Additive primes: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 1,988: Line 1,988:


=={{header|Rust}}==
=={{header|Rust}}==

===Flat implementation===
<lang Rust>
<lang Rust>
fn main() {
fn main() {
let limit = 500;
let limit = 500;
//all primes, starting from 3 (including non-additive), will be collected in pms
//all primes, starting from 3 (including non-additive), will be collected in pms
// it works ~1.5 times faster than the variant with fn is_prime()
// it works ~1.5 times faster than the variant with fn is_prime(){...while...+=6...}
let mut pms = Vec::with_capacity(limit / 2 - limit / 3 / 2 - limit / 5 / 3 / 2 + 1);
let mut pms = Vec::with_capacity(limit / 2 - limit / 3 / 2 - limit / 5 / 3 / 2 + 1);
let column_width = limit.to_string().len() + 1;
let column_width = limit.to_string().len() + 1;
Line 2,011: Line 2,013:
}
}
}
}
}
println!("\n---\nFound {} additive primes less than {}", count, limit);
}
</lang>
{{out}}
<pre>
2 3 5 7 11 23 29 41 43 47
61 67 83 89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487
---
Found 54 additive primes less than 500
</pre>


===With crate "primal"===
primal implements the sieve of Eratosthenes with optimizations (10+ times faster for large limits)

<lang Rust>
// [dependencies]
// primal = "0.3.0"

use primal::Sieve;

fn main() {
let limit = 500;
let column_width = limit.to_string().len() + 1;
let sieve_primes = Sieve::new(limit);
let mut count = 0;
for u in sieve_primes.primes_from(2).filter(|&p| {
p < limit
&& sieve_primes.is_prime(
std::iter::successors(Some(p), |&n| (n > 9).then(|| n / 10))
.fold(0, |s, n| s + n % 10),
)
}) {
if count % 10 == 0 {
println!();
}
print!("{:1$}", u, column_width);
count += 1;
}
}
println!("\n---\nFound {} additive primes less than {}", count, limit);
println!("\n---\nFound {} additive primes less than {}", count, limit);

Revision as of 21:30, 14 November 2021

Task
Additive primes
You are encouraged to solve this task according to the task description, using any language you may know.
Definitions

In mathematics, additive primes are prime numbers for which the sum of their decimal digits are also primes.


Task

Write a program to determine (and show here) all additive primes less than 500.

Optionally, show the number of additive primes.


Also see



Ada

<lang Ada>with Ada.Text_Io;

procedure Additive_Primes is 

  Last    : constant := 499;
  Columns : constant := 12;

  type Prime_List is array (2 .. Last) of Boolean;

  function Get_Primes return Prime_List is
     Prime : Prime_List := (others => True);
  begin
     for P in Prime'Range loop
        if Prime (P) then
           for N in 2 .. Positive'Last loop
              exit when N * P not in Prime'Range;
              Prime (N * P) := False;
           end loop;
        end if;
     end loop;
     return Prime;
  end Get_Primes;

  function Sum_Of (N : Natural) return Natural is
     Image : constant String := Natural'Image (N);
     Sum   : Natural := 0;
  begin
     for Char of Image loop
        Sum := Sum + (if Char in '0' .. '9'
                      then Natural'Value ("" & Char)
                      else 0);
     end loop;
     return Sum;
  end Sum_Of;

  package Natural_Io is new Ada.Text_Io.Integer_Io (Natural);
  use Ada.Text_Io, Natural_Io;

  Prime : constant Prime_List := Get_Primes;
  Count : Natural := 0;

begin 

  Put_Line ("Additive primes <500:");
  for N in Prime'Range loop
     if Prime (N) and then Prime (Sum_Of (N)) then
        Count := Count + 1;
        Put (N, Width => 5);
        if Count mod Columns = 0 then
           New_Line;
        end if;
     end if;
  end loop;
  New_Line;

  Put ("There are ");
  Put (Count, Width => 2);
  Put (" additive primes.");
  New_Line;

end Additive_Primes;</lang>

Output:
Additive primes <500:
    2    3    5    7   11   23   29   41   43   47   61   67
   83   89  101  113  131  137  139  151  157  173  179  191
  193  197  199  223  227  229  241  263  269  281  283  311
  313  317  331  337  353  359  373  379  397  401  409  421
  443  449  461  463  467  487
There are 54 additive primes.

ALGOL 68

Library: ALGOL 68-primes

<lang algol68>BEGIN # find additive primes - primes whose digit sum is also prime # 

   # sieve the primes to max prime #
   PR read "primes.incl.a68" PR
   []BOOL prime = PRIMESIEVE 499;
   # find the additive primes #
   INT additive count := 0;
   FOR n TO UPB prime DO
       IF prime[ n ] THEN
           # have a prime #
           INT digit sum := 0;
           INT v         := n;
           WHILE v > 0 DO
               digit sum +:= v MOD 10;
               v OVERAB 10
           OD;
           IF prime( digit sum ) THEN
               # the digit sum is prime #
               print( ( " ", whole( n, -3 ) ) );
               IF ( additive count +:= 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI
           FI
       FI
   OD;
   print( ( newline, "Found ", whole( additive count, 0 ), " additive primes below ", whole( UPB prime + 1, 0 ), newline ) )

END</lang>

Output:
   2   3   5   7  11  23  29  41  43  47  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449 461 463 467 487
Found 54 additive primes below 500

ALGOL W

<lang algolw>begin % find some additive primes - primes whose digit sum is also prime % 

   % sets p( 1 :: n ) to a sieve of primes up to n %
   procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
   begin
       p( 1 ) := false; p( 2 ) := true;
       for i := 3 step 2 until n do p( i ) := true;
       for i := 4 step 2 until n do p( i ) := false;
       for i := 3 step 2 until truncate( sqrt( n ) ) do begin
           integer ii; ii := i + i;
           if p( i ) then for pr := i * i step ii until n do p( pr ) := false
       end for_i ;
   end Eratosthenes ;
   integer MAX_NUMBER;
   MAX_NUMBER := 500;
   begin
       logical array prime( 1 :: MAX_NUMBER );
       integer       aCount;
       % sieve the primes to MAX_NUMBER %
       Eratosthenes( prime, MAX_NUMBER );
       % find the primes that are additive primes %
       aCount := 0;
       for i := 1 until MAX_NUMBER - 1 do begin
           if prime( i ) then begin
               integer dSum, v;
               v    := i;
               dSum := 0;
               while v > 0 do begin
                   dSum := dSum + v rem 10;
                   v    := v div 10
               end while_v_gt_0 ;
               if prime( dSum ) then begin
                   writeon( i_w := 4, s_w := 0, " ", i );
                   aCount := aCount + 1;
                   if aCount rem 20 = 0 then write()
               end if_prime_dSum
           end if_prime_i
       end for_i ;
       write( i_w := 1, s_w := 0, "Found ", aCount, " additive primes below ", MAX_NUMBER )
   end

end.</lang>

Output:
    2    3    5    7   11   23   29   41   43   47   61   67   83   89  101  113  131  137  139  151
  157  173  179  191  193  197  199  223  227  229  241  263  269  281  283  311  313  317  331  337
  353  359  373  379  397  401  409  421  443  449  461  463  467  487
Found 54 additive primes below 500

APL

<lang APL>((+⌿(4/10)⊤P)∊P)/P←(~P∊P∘.×P)/P←1↓⍳500</lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283
      311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487

AppleScript

<lang applescript>on sieveOfEratosthenes(limit) 

   script o
       property numberList : {missing value}
   end script
   
   repeat with n from 2 to limit
       set end of o's numberList to n
   end repeat
   
   repeat with n from 2 to (limit ^ 0.5) div 1
       if (item n of o's numberList is n) then
           repeat with multiple from n * n to limit by n
               set item multiple of o's numberList to missing value
           end repeat
       end if
   end repeat
   
   return o's numberList's numbers

end sieveOfEratosthenes

on sumOfDigits(n) -- n assumed to be a positive decimal integer. 

   set sum to n mod 10
   set n to n div 10
   repeat until (n = 0)
       set sum to sum + n mod 10
       set n to n div 10
   end repeat
   
   return sum

end sumOfDigits

on additivePrimes(limit) 

   script o
       property primes : sieveOfEratosthenes(limit)
       property additives : {}
   end script
   
   repeat with p in o's primes
       if (sumOfDigits(p) is in o's primes) then set end of o's additives to p's contents
   end repeat
   
   return o's additives

end additivePrimes

-- Task code: tell additivePrimes(499) to return {|additivePrimes<500|:it, numberThereof:count}</lang>

Output:

<lang applescript>{|additivePrimes<500|:{2, 3, 5, 7, 11, 23, 29, 41, 43, 47, 61, 67, 83, 89, 101, 113, 131, 137, 139, 151, 157, 173, 179, 191, 193, 197, 199, 223, 227, 229, 241, 263, 269, 281, 283, 311, 313, 317, 331, 337, 353, 359, 373, 379, 397, 401, 409, 421, 443, 449, 461, 463, 467, 487}, numberThereof:54}</lang>

Arturo

<lang rebol>additives: select 2..500 'x -> and? prime? x prime? sum digits x

loop split.every:10 additives 'a -> 

   print map a => [pad to :string & 4]

print ["\nFound" size additives "additive primes up to 500"]</lang>

Output:
   2    3    5    7   11   23   29   41   43   47 
  61   67   83   89  101  113  131  137  139  151 
 157  173  179  191  193  197  199  223  227  229 
 241  263  269  281  283  311  313  317  331  337 
 353  359  373  379  397  401  409  421  443  449 
 461  463  467  487 

Found 54 additive primes up to 500

AWK

<lang AWK>

  1. syntax: GAWK -f ADDITIVE_PRIMES.AWK

BEGIN { 

   start = 1
   stop = 500
   for (i=start; i<=stop; i++) {
     if (is_prime(i) && is_prime(sum_digits(i))) {
       printf("%4d%1s",i,++count%10?"":"\n")
     }
   }
   printf("\nAdditive primes %d-%d: %d\n",start,stop,count)
   exit(0)

} function is_prime(x, i) { 

   if (x <= 1) {
     return(0)
   }
   for (i=2; i<=int(sqrt(x)); i++) {
     if (x % i == 0) {
       return(0)
     }
   }
   return(1)

} function sum_digits(n, i,sum) { 

   for (i=1; i<=length(n); i++) {
     sum += substr(n,i,1)
   }
   return(sum)

} </lang>

Output:
   2    3    5    7   11   23   29   41   43   47
  61   67   83   89  101  113  131  137  139  151
 157  173  179  191  193  197  199  223  227  229
 241  263  269  281  283  311  313  317  331  337
 353  359  373  379  397  401  409  421  443  449
 461  463  467  487
Additive primes 1-500: 54

BASIC

<lang basic>10 DEFINT A-Z: E=500 20 DIM P(E): P(0)=-1: P(1)=-1 30 FOR I=2 TO SQR(E) 40 IF NOT P(I) THEN FOR J=I*2 TO E STEP I: P(J)=-1: NEXT 50 NEXT 60 FOR I=B TO E: IF P(I) GOTO 100 70 J=I: S=0 80 IF J>0 THEN S=S+J MOD 10: J=J\10: GOTO 80 90 IF NOT P(S) THEN N=N+1: PRINT I, 100 NEXT 110 PRINT: PRINT N;" additive primes found below ";E</lang>

Output:
 2             3             5             7             11
 23            29            41            43            47
 61            67            83            89            101
 113           131           137           139           151
 157           173           179           191           193
 197           199           223           227           229
 241           263           269           281           283
 311           313           317           331           337
 353           359           373           379           397
 401           409           421           443           449
 461           463           467           487
 54  additive primes found below  500

BCPL

<lang bcpl>get "libhdr" manifest $( limit = 500 $)

let dsum(n) = 

   n=0 -> 0,
   dsum(n/10) + n rem 10

let sieve(prime, n) be $( 0!prime := false 

   1!prime := false
   for i=2 to n do i!prime := true
   for i=2 to n/2
       if i!prime 
       $(  let j=i+i
           while j<=n
           $(  j!prime := false
               j := j+i
           $)
       $)

$)

let additive(prime, n) = n!prime & dsum(n)!prime

let start() be $( let prime = vec limit 

   let num = 0
   sieve(prime, limit)
   for i=2 to limit
       if additive(prime,i)
       $(  writed(i,5)
           num := num + 1
           if num rem 10 = 0 then wrch('*N')
       $)
   writef("*N*NFound %N additive primes < %N.*N", num, limit)

$)</lang>

Output:
    2    3    5    7   11   23   29   41   43   47
   61   67   83   89  101  113  131  137  139  151
  157  173  179  191  193  197  199  223  227  229
  241  263  269  281  283  311  313  317  331  337
  353  359  373  379  397  401  409  421  443  449
  461  463  467  487

Found 54 additive primes < 500.

C

<lang C>

  1. include <stdbool.h>
  2. include <stdio.h>
  3. include <string.h>

void memoizeIsPrime( bool * result, const int N ) { 

   result[2] = true;
   result[3] = true;
   int prime[N];
   prime[0] = 3;
   int end = 1;
   for (int n = 5; n < N; n += 2)
   {
       bool n_is_prime = true;
       for (int i = 0; i < end; ++i)
       {
           const int PRIME = prime[i];
           if (n % PRIME == 0)
           {
               n_is_prime = false;
               break;
           }
           if (PRIME * PRIME > n)
           {
               break;
           }
       }
       if (n_is_prime)
       {
           prime[end++] = n;
           result[n] = true;
       }
   }

}/* memoizeIsPrime */

int sumOfDecimalDigits( int n ) { 

   int sum = 0;
   while (n > 0)
   {
       sum += n % 10;
       n /= 10;
   }
   return sum;

}/* sumOfDecimalDigits */

int main( void ) { 

   const int N = 500;

   printf( "Rosetta Code: additive primes less than %d:\n", N );

   bool is_prime[N];
   memset( is_prime, 0, sizeof(is_prime) );
   memoizeIsPrime( is_prime, N );

   printf( "   2" );
   int count = 1;
   for (int i = 3; i < N; i += 2)
   {
       if (is_prime[i] && is_prime[sumOfDecimalDigits( i )])
       {
           printf( "%4d", i );
           ++count;
           if ((count % 10) == 0)
           {
               printf( "\n" );
           }
       }
   }
   printf( "\nThose were %d additive primes.\n", count );
   return 0;

}/* main */ </lang>

Output:
Rosetta Code: additive primes less than 500:
   2   3   5   7  11  23  29  41  43  47
  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449
 461 463 467 487
Those were 54 additive primes.

C++

<lang cpp>#include <iomanip>

  1. include <iostream>

bool is_prime(unsigned int n) { 

   if (n < 2)
       return false;
   if (n % 2 == 0)
       return n == 2;
   if (n % 3 == 0)
       return n == 3;
   for (unsigned int p = 5; p * p <= n; p += 4) {
       if (n % p == 0)
           return false;
       p += 2;
       if (n % p == 0)
           return false;
   }
   return true;

}

unsigned int digit_sum(unsigned int n) { 

   unsigned int sum = 0;
   for (; n > 0; n /= 10)
       sum += n % 10;
   return sum;

}

int main() { 

   const unsigned int limit = 500;
   std::cout << "Additive primes less than " << limit << ":\n";
   unsigned int count = 0;
   for (unsigned int n = 1; n < limit; ++n) {
       if (is_prime(digit_sum(n)) && is_prime(n)) {
           std::cout << std::setw(3) << n;
           if (++count % 10 == 0)
               std::cout << '\n';
           else
               std::cout << ' ';
       }
   }
   std::cout << '\n' << count << " additive primes found.\n";

}</lang>

Output:
Additive primes less than 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487 
54 additive primes found.


COBOL

<lang cobol> IDENTIFICATION DIVISION. 

      PROGRAM-ID. ADDITIVE-PRIMES.
      
      DATA DIVISION.
      WORKING-STORAGE SECTION.
      01 VARIABLES.
         03 MAXIMUM            PIC 999.
         03 AMOUNT             PIC 999.
         03 CANDIDATE          PIC 999.
         03 DIGIT              PIC 9 OCCURS 3 TIMES, 
                               REDEFINES CANDIDATE.
         03 DIGITSUM           PIC 99.
         
      01 PRIME-DATA.
         03 COMPOSITE-FLAG     PIC X OCCURS 500 TIMES.
            88 PRIME           VALUE ' '.
         03 SIEVE-PRIME        PIC 999.
         03 SIEVE-COMP-START   PIC 999.
         03 SIEVE-COMP         PIC 999.
         03 SIEVE-MAX          PIC 999.
      
      01 OUT-FMT.
         03 NUM-FMT            PIC ZZZ9.
         03 OUT-LINE           PIC X(40).
         03 OUT-PTR            PIC 99.
         
      PROCEDURE DIVISION.
      BEGIN.
          MOVE 500 TO MAXIMUM.
          MOVE 1 TO OUT-PTR.
          PERFORM SIEVE.
          MOVE ZERO TO AMOUNT.
          PERFORM TEST-NUMBER 
              VARYING CANDIDATE FROM 2 BY 1
              UNTIL CANDIDATE IS GREATER THAN MAXIMUM.
          DISPLAY OUT-LINE.
          DISPLAY SPACES.
          MOVE AMOUNT TO NUM-FMT.
          DISPLAY 'Amount of additive primes found: ' NUM-FMT.
          STOP RUN.

      TEST-NUMBER.
          ADD DIGIT(1), DIGIT(2), DIGIT(3) GIVING DIGITSUM.
          IF PRIME(CANDIDATE) AND PRIME(DIGITSUM),
              ADD 1 TO AMOUNT,
              PERFORM WRITE-NUMBER.
      
      WRITE-NUMBER.
          MOVE CANDIDATE TO NUM-FMT.
          STRING NUM-FMT DELIMITED BY SIZE INTO OUT-LINE 
              WITH POINTER OUT-PTR.
          IF OUT-PTR IS GREATER THAN 40,
              DISPLAY OUT-LINE,
              MOVE SPACES TO OUT-LINE,
              MOVE 1 TO OUT-PTR.               
      
      SIEVE.
          MOVE SPACES TO PRIME-DATA.
          DIVIDE MAXIMUM BY 2 GIVING SIEVE-MAX.
          PERFORM SIEVE-OUTER-LOOP
              VARYING SIEVE-PRIME FROM 2 BY 1
              UNTIL SIEVE-PRIME IS GREATER THAN SIEVE-MAX.
         
      SIEVE-OUTER-LOOP.
          IF PRIME(SIEVE-PRIME),
              MULTIPLY SIEVE-PRIME BY 2 GIVING SIEVE-COMP-START,
              PERFORM SIEVE-INNER-LOOP
                  VARYING SIEVE-COMP 
                      FROM SIEVE-COMP-START BY SIEVE-PRIME
                  UNTIL SIEVE-COMP IS GREATER THAN MAXIMUM.
      
      SIEVE-INNER-LOOP.
          MOVE 'X' TO COMPOSITE-FLAG(SIEVE-COMP).</lang>
Output:
   2   3   5   7  11  23  29  41  43  47
  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449
 461 463 467 487

Amount of additive primes found:   54

Common Lisp

<lang lisp> (defun sum-of-digits (n) 

"Return the sum of the digits of a number"
 (do* ((sum 0 (+ sum rem))
       rem )
      ((zerop n) sum)
   (multiple-value-setq (n rem) (floor n 10)) ))

(defun additive-primep (n) 

 (and (primep n) (primep (sum-of-digits n))) )


To test if a number is prime we can use a number of different methods. Here I use Wilson's Theorem (see Primality by Wilson's theorem)

(defun primep (n) 

 (unless (zerop n)
   (zerop (mod (1+ (factorial (1- n))) n)) ))

(defun factorial (n) 

 (if (< n 2) 1 (* n (factorial (1- n)))) )


</lang>

Output:
(dotimes (i 500) (when (additive-primep i) (princ i) (princ " ")))

1 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487

F#

This task uses Extensible Prime Generator (F#) <lang fsharp> // Additive Primes. Nigel Galloway: March 22nd., 2021 let rec fN g=function n when n<10->n+g |n->fN(g+n%10)(n/10) primes32()|>Seq.takeWhile((>)500)|>Seq.filter(fN 0>>isPrime)|>Seq.iter(printf "%d "); printfn "" </lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: formatting grouping io kernel math math.primes prettyprint sequences ;

sum-digits ( n -- sum )
   0 swap [ 10 /mod rot + swap ] until-zero ;

499 primes-upto [ sum-digits prime? ] filter [ 9 group simple-table. nl ] [ length "Found %d additive primes < 500.\n" printf ] bi</lang>

Output:
2   3   5   7   11  23  29  41  43
47  61  67  83  89  101 113 131 137
139 151 157 173 179 191 193 197 199
223 227 229 241 263 269 281 283 311
313 317 331 337 353 359 373 379 397
401 409 421 443 449 461 463 467 487

Found  54  additive primes  <  500.

Fermat

<lang fermat>Function Digsum(n) = 

   digsum := 0;
   while n>0 do
       digsum := digsum + n|10;
       n:=n\10;
   od;
   digsum.;

nadd := 0; !!'Additive primes below 500 are';

for p=1 to 500 do 

   if Isprime(p) and Isprime(Digsum(p)) then
      !!(p,' -> ',Digsum(p));
      nadd := nadd+1;
   fi od;

!!('There were ',nadd);</lang>

Output:


Additive primes below 500 are



2 ->  2
3 ->  3
5 ->  5
7 ->  7
11 ->  2
23 ->  5
29 ->  11
41 ->  5
43 ->  7
47 ->  11
61 ->  7
67 ->  13
83 ->  11
89 ->  17
101 ->  2
113 ->  5
131 ->  5
137 ->  11
139 ->  13
151 ->  7
157 ->  13
173 ->  11
179 ->  17
191 ->  11
193 ->  13
197 ->  17
199 ->  19
223 ->  7
227 ->  11
229 ->  13
241 ->  7
263 ->  11
269 ->  17
281 ->  11
283 ->  13
311 ->  5
313 ->  7
317 ->  11
331 ->  7
337 ->  13
353 ->  11
359 ->  17
373 ->  13
379 ->  19
397 ->  19
401 ->  5
409 ->  13
421 ->  7
443 ->  11
449 ->  17
461 ->  11
463 ->  13
467 ->  17
487 ->  19


There were  54

Forth

Works with: Gforth

<lang forth>: prime? ( n -- ? ) here + c@ 0= ;

notprime! ( n -- ) here + 1 swap c! ;
prime_sieve ( n -- )
 here over erase
 0 notprime!
 1 notprime!
 2
 begin
   2dup dup * >
 while
   dup prime? if
     2dup dup * do
       i notprime!
     dup +loop
   then
   1+
 repeat
 2drop ;
digit_sum ( u -- u )
 dup 10 < if exit then
 10 /mod recurse + ;
print_additive_primes ( n -- )
 ." Additive primes less than " dup 1 .r ." :" cr
 dup prime_sieve
 0 swap
 1 do
   i prime? if
     i digit_sum prime? if
       i 3 .r
       1+ dup 10 mod 0= if cr else space then
     then
   then
 loop
 cr . ." additive primes found." cr ;

500 print_additive_primes bye</lang>

Output:
Additive primes less than 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487 
54 additive primes found.

FreeBASIC

As with the other special primes tasks, use one of the primality testing algorithms as an include. <lang freebasic>#include "isprime.bas"

function digsum( n as uinteger ) as uinteger 

   dim as uinteger s
   while n
       s+=n mod 10
       n\=10
   wend
   return s

end function

dim as uinteger s

print "Prime","Digit Sum" for i as uinteger = 2 to 499 

   if isprime(i) then
       s = digsum(i)
       if isprime(s) then
           print i, s
       end if
   end if

next i</lang>

Output:
Prime         Digit Sum
2             2
3             3
5             5
7             7
11            2
23            5
29            11
41            5
43            7
47            11
61            7
67            13
83            11
89            17
101           2
113           5
131           5
137           11
139           13
151           7
157           13
173           11
179           17
191           11
193           13
197           17
199           19
223           7
227           11
229           13
241           7
263           11
269           17
281           11
283           13
311           5
313           7
317           11
331           7
337           13
353           11
359           17
373           13
379           19
397           19
401           5
409           13
421           7
443           11
449           17
461           11
463           13
467           17
487           19

Go

<lang go>package main

import "fmt"

func isPrime(n int) bool { 

   switch {
   case n < 2:
       return false
   case n%2 == 0:
       return n == 2
   case n%3 == 0:
       return n == 3
   default:
       d := 5
       for d*d <= n {
           if n%d == 0 {
               return false
           }
           d += 2
           if n%d == 0 {
               return false
           }
           d += 4
       }
       return true
   }

}

func sumDigits(n int) int { 

   sum := 0
   for n > 0 {
       sum += n % 10
       n /= 10
   }
   return sum

}

func main() { 

   fmt.Println("Additive primes less than 500:")
   i := 2
   count := 0
   for {
       if isPrime(i) && isPrime(sumDigits(i)) {
           count++
           fmt.Printf("%3d  ", i)
           if count%10 == 0 {
               fmt.Println()
           }
       }
       if i > 2 {
           i += 2
       } else {
           i++
       }
       if i > 499 {
           break
       }
   }
   fmt.Printf("\n\n%d additive primes found.\n", count)

}</lang>

Output:
Additive primes less than 500:
  2    3    5    7   11   23   29   41   43   47  
 61   67   83   89  101  113  131  137  139  151  
157  173  179  191  193  197  199  223  227  229  
241  263  269  281  283  311  313  317  331  337  
353  359  373  379  397  401  409  421  443  449  
461  463  467  487
 
54 additive primes found.

Java

<lang Java>public class additivePrimes { 

   public static void main(String[] args) {
       int additive_primes = 0;
       for (int i = 2; i < 500; i++) {
           if(isPrime(i) && isPrime(digitSum(i))){
               additive_primes++;
               System.out.print(i + " ");
           }
       }
       System.out.print("\nFound " + additive_primes + " additive primes less than 500");
   }

   static boolean isPrime(int n) {
       int counter = 1;
       if (n < 2 || (n != 2 && n % 2 == 0) || (n != 3 && n % 3 == 0)) {
           return false;
       }
       while (counter * 6 - 1 <= Math.sqrt(n)) {
           if (n % (counter * 6 - 1) == 0 || n % (counter * 6 + 1) == 0) {
               return false;
           } else {
               counter++;
           }
       }
       return true;
   }

   static int digitSum(int n) {
       int sum = 0;
       while (n > 0) {
           sum += n % 10;
           n /= 10;
       }
       return sum;
   }

} </lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 
Found 54 additive primes less than 500

jq

Works with: jq

Works with gojq, the Go implementation of jq

Preliminaries <lang jq>def is_prime: 

 . as $n
 | if ($n < 2)         then false
   elif ($n % 2 == 0)  then $n == 2
   elif ($n % 3 == 0)  then $n == 3
   elif ($n % 5 == 0)  then $n == 5
   elif ($n % 7 == 0)  then $n == 7
   elif ($n % 11 == 0) then $n == 11
   elif ($n % 13 == 0) then $n == 13
   elif ($n % 17 == 0) then $n == 17
   elif ($n % 19 == 0) then $n == 19
   else {i:23}
   | until( (.i * .i) > $n or ($n % .i == 0); .i += 2)
   | .i * .i > $n
   end;
  1. Emit an array of primes less than `.`

def primes: 

 if . < 2 then []
 else [2] + [range(3; .; 2) | select(is_prime)]
 end;

def add(s): reduce s as $x (null; . + $x);

def sumdigits: add(tostring | explode[] | [.] | implode | tonumber);

  1. Pretty-printing

def nwise($n): 

 def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
 n;

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; </lang> The task <lang jq>

  1. Input: a number n
  2. Output: an array of additive primes less than n

def additive_primes: 

 primes
 | . as $primes
 | reduce .[] as $p (null;
     ( $p | sumdigits ) as $sum
     | if (($primes | bsearch($sum)) > -1)
       then . + [$p]
       else .
       end );

"Erdős primes under 500:", (500 | additive_primes 

| ((nwise(10) | map(lpad(4)) | join(" ")),
  "\n\(length) additive primes found."))
</lang>
Output:
Erdős primes under 500:
   2    3    5    7   11   23   29   41   43   47
  61   67   83   89  101  113  131  137  139  151
 157  173  179  191  193  197  199  223  227  229
 241  263  269  281  283  311  313  317  331  337
 353  359  373  379  397  401  409  421  443  449
 461  463  467  487

54 additive primes found.

Haskell

Naive solution which doesn't rely on advanced number theoretic libraries. <lang haskell>import Data.List (unfoldr)

-- infinite list of primes primes = 2 : sieve [3,5..] 

 where sieve (x:xs) = x : sieve (filter (\y -> y `mod` x /= 0) xs)

-- primarity test, effective for numbers less then billion isPrime n = all (\p -> n `mod` p /= 0) $ takeWhile (< sqrtN) primes 

 where sqrtN = round . sqrt . fromIntegral $ n

-- decimal digits of a number digits = unfoldr f 

 where f 0 = Nothing
       f n = let (q, r) = divMod n 10 in Just (r,q)

-- test for an additive prime isAdditivePrime n = isPrime n && (isPrime . sum . digits) n </lang>

The task 

λ> isPrime 12373
True

λ> isAdditivePrime 12373
False

λ> isPrime 12347
True

λ> isAdditivePrime 12347
True

λ> takeWhile (< 500) $ filter isAdditivePrime primes
[2,3,5,7,11,13,23,29,31,41,43,47,61,67,83,89,101,103,113,131,137,139,151,157,173,179,191,193,197,199,211,223,227,229,241,263,269,281,283,311,313,317,331,337,353,359,373,379,397,401,409,421,443,449,461,463,467,487]

Julia

<lang julia>using Primes

let 

   p = primesmask(500)
   println("Additive primes under 500:")
   pcount = 0
   for i in 2:499
       if p[i] && p[sum(digits(i))]
           pcount += 1
           print(lpad(i, 4), pcount % 20 == 0 ? "\n" : "")
       end
   end
   println("\n\n$pcount additive primes found.")

end

</lang>

Output:
Erdős primes under 500:
   2   3   5   7  11  23  29  41  43  47  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449 461 463 467 487

54 additive primes found.

Kotlin

Translation of: Python

<lang kotlin>fun isPrime(n: Int): Boolean { 

   if (n <= 3) return n > 1
   if (n % 2 == 0 || n % 3 == 0) return false
   var i = 5
   while (i * i <= n) {
       if (n % i == 0 || n % (i + 2) == 0) return false
       i += 6
   }
   return true

}

fun digitSum(n: Int): Int { 

   var sum = 0
   var num = n
   while (num > 0) {
       sum += num % 10
       num /= 10
   }
   return sum

}

fun main() { 

   var additivePrimes = 0
   for (i in 2 until 500) {
       if (isPrime(i) and isPrime(digitSum(i))) {
           additivePrimes++
           print("$i ")
       }
   }
   println("\nFound $additivePrimes additive primes less than 500")

}</lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 
Found 54 additive primes less than 500

Ksh

<lang ksh>#!/bin/ksh

  1. Prime numbers for which the sum of their decimal digits are also primes
  1. # Variables:

integer MAX_n=500

  1. # Functions:
  3. # Function _isprime(n) return 1 for prime, 0 for not prime

function _isprime { typeset _n ; integer _n=$1 typeset _i ; integer _i

(( _n < 2 )) && return 0 for (( _i=2 ; _i*_i<=_n ; _i++ )); do (( ! ( _n % _i ) )) && return 0 done return 1 }

  1. # Function _sumdigits(n) return sum of n's digits

function _sumdigits { typeset _n ; _n=$1 typeset _i _sum ; integer _i _sum=0

for ((_i=0; _i<${#_n}; _i++)); do (( _sum+=${_n:${_i}:1} )) done echo ${_sum} } 

######
  1. main #
######

integer i digsum for ((i=2; i<MAX_n; i++)); do _isprime ${i} && (( ! $? )) && continue

digsum=$(_sumdigits ${i}) _isprime ${digsum} ; (( $? )) && printf "%4d " ${i} done print

Output:
   2    3    5    7   11   23   29   41   43   47   61   67   83   89  101  113  131  137  139  151  157  173  179  191  193  197  199  223  227  229  241  263  269  281  283  311  313  317  331  337  353  359  373  379  397  401  409  421  443  449  461  463  467  487


Lua

This task uses primegen from: Extensible_prime_generator#Lua <lang lua>function sumdigits(n) 

 local sum = 0
 while n > 0 do
   sum = sum + n % 10
   n = math.floor(n/10)
 end
 return sum

end

primegen:generate(nil, 500) aprimes = primegen:filter(function(n) return primegen.tbd(sumdigits(n)) end) print(table.concat(aprimes, " ")) print("Count:", #aprimes)</lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487
Count:  54

Mathematica/Wolfram Language

<lang Mathematica>ClearAll[AdditivePrimeQ] AdditivePrimeQ[n_Integer] := PrimeQ[n] \[And] PrimeQ[Total[IntegerDigits[n]]] Select[Range[500], AdditivePrimeQ]</lang>

Output:
{2,3,5,7,11,23,29,41,43,47,61,67,83,89,101,113,131,137,139,151,157,173,179,191,193,197,199,223,227,229,241,263,269,281,283,311,313,317,331,337,353,359,373,379,397,401,409,421,443,449,461,463,467,487}

Modula-2

<lang modula2>MODULE AdditivePrimes; FROM InOut IMPORT WriteString, WriteCard, WriteLn;

CONST 

   Max = 500;

VAR 

   N: CARDINAL;
   Count: CARDINAL;
   Prime: ARRAY [2..Max] OF BOOLEAN;

PROCEDURE DigitSum(n: CARDINAL): CARDINAL; BEGIN 

   IF n < 10 THEN 
       RETURN n;
   ELSE 
       RETURN (n MOD 10) + DigitSum(n DIV 10);
   END;

END DigitSum;

PROCEDURE Sieve; VAR i, j, max2: CARDINAL; BEGIN 

   FOR i := 2 TO Max DO
       Prime[i] := TRUE;
   END;
   
   FOR i := 2 TO Max DIV 2 DO
       IF Prime[i] THEN;
           j := i*2;
           WHILE j <= Max DO 
               Prime[j] := FALSE;
               j := j + i;
           END;
       END;
   END;

END Sieve;

BEGIN 

   Count := 0;
   Sieve();
   FOR N := 2 TO Max DO
       IF Prime[N] AND Prime[DigitSum(N)] THEN
           WriteCard(N, 4);
           Count := Count + 1;
           IF Count MOD 10 = 0 THEN WriteLn(); END;
       END;
   END;
   WriteLn();
   WriteString('There are '); WriteCard(Count,0);
   WriteString(' additive primes less than '); WriteCard(Max,0);
   WriteString('.');
   WriteLn();

END AdditivePrimes.</lang>

Output:
   2   3   5   7  11  23  29  41  43  47
  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449
 461 463 467 487
There are 54 additive primes less than 500.

Nim

<lang Nim>import math, strutils

const N = 499

  1. Sieve of Erathostenes.

var composite: array[2..N, bool] # Initialized to false, ie. prime.

for n in 2..sqrt(N.toFloat).int: 

 if not composite[n]:
   for k in countup(n * n, N, n):
     composite[k] = true


func digitSum(n: Positive): Natural = 

 ## Compute sum of digits.
 var n = n.int
 while n != 0:
   result += n mod 10
   n = n div 10


echo "Additive primes less than 500:" var count = 0 for n in 2..N: 

 if not composite[n] and not composite[digitSum(n)]:
   inc count
   stdout.write ($n).align(3)
   stdout.write if count mod 10 == 0: '\n' else: ' '

echo()

echo "\nNumber of additive primes found: ", count</lang>

Output:
Additive primes less than 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487 

Number of additive primes found: 54

Pari/GP

This is a good task for demonstrating several different ways to approach a simple problem. <lang parigp>hasPrimeDigitsum(n)=isprime(sumdigits(n)); \\ see A028834 in the OEIS

v1 = select(isprime, select(hasPrimeDigitsum, [1..499])); v2 = select(hasPrimeDigitsum, select(isprime, [1..499])); v3 = select(hasPrimeDigitsum, primes([1, 499]));

s=0; forprime(p=2,499, if(hasPrimeDigitsum(p), s++)); s; [#v1, #v2, #v3, s]</lang>

Output:
%1 = [54, 54, 54, 54]

Pascal

Works with: Free Pascal

checking isPrime(sum of digits) before testimg isprime(num) improves speed.
Tried to speed up calculation of sum of digits.

<lang pascal>program AdditivePrimes; {$IFDEF FPC} 

 {$MODE DELPHI}{$CODEALIGN proc=16}

{$ELSE} 

 {$APPTYPE CONSOLE}

{$ENDIF} {$DEFINE DO_OUTPUT} uses 

 sysutils;

const 

 RANGE = 500;//1000*1000;//
 MAX_OFFSET = 0;//1000*1000*1000;//
 ColWidth = Trunc(ln(MAX_OFFSET+RANGE)/ln(10))+2;
 MAXCOLUMNS = 80;
 NextRowCnt = MAXCOLUMNS DIV ColWidth;

type 

 tNum = array[0..15] of byte;
 tNumSum = record
             dgtNum,
             dgtSum: tNum;
             dgtLen,
             num : Uint32;
           end;
 tpNumSum = ^tNumSum;

function isPrime(n:Uint32):boolean; const 

 wheeldiff : array[0..7] of Uint32 = (+6,+4,+2,+4,+2,+4,+6,+2);

var 

 p: NativeUInt;
 flipflop : Int32;

begin 

 if n< 64 then
   EXIT(n in [  2,3,5,7,11,13,17,19,23,29,
             31,     37,41,43,47,   53,59,61])
 else
 begin
   IF (n AND 1=0) OR (n mod 3 = 0 ) OR (n mod 5 = 0 ) then
     EXIT(false);
   result := true;
   p := 1;
   flipflop := 6;

   while result do
   Begin
     p += wheeldiff[flipflop];
     if p*p>n then
       BREAK;
     result := n mod p <> 0;
     flipflop -= 1;
     if flipflop<0 then
       flipflop :=7;
   end
 end

end;

procedure IncNum(var NumSum: tNumSum;delta: Uint32); const 

 BASE = 10;

var 

 carry,
 dg: UInt32;
 le : Int32;

Begin 

 if delta = 0 then
   EXIT;
 le := 0;
 with NumSum do
 begin
   num +=delta;
   repeat
     carry := delta div BASE;
     delta -= BASE*carry;
     dg := dgtNum[le]+delta;
     IF dg >= BASE then
     Begin
       dg -= BASE;
       inc(carry);
     end;
     dgtNum[le] := dg;
     inc(le);
     delta := carry;
   until carry = 0;
   if dgtLen < le then
     dgtLen := le;
   //correct sum of digits // le is >= 1
   delta := dgtSum[le];
   repeat
     dec(le);
     delta+= dgtNum[le];
     dgtSum[le]:= delta;
   until le = 0;
 end;

end;

var 

 NumSum: tNumSum;
 s : AnsiString;
 i,k,cnt,Nr: NativeUint;

BEGIN 

 fillchar(NumSum,SizeOf(NumSum),#0);
 NumSum.dgtLen := 1;
 IncNum(NumSum,MAX_OFFSET);
 setlength(s,ColWidth);
 fillchar(s[1],ColWidth,' ');
 //init string
 with Numsum do
 Begin
   For i := dgtlen-1 downto 0 do
     s[ColWidth-i] := chr(dgtNum[i]+48);
   //reset digits lenght to get the max changed digits since last update of string
   dgtlen := 0;
 end;
 cnt := 0;
 Nr := NextRowCnt;
 For i := 0 to RANGE do
 with NumSum do
   begin
   if isprime(dgtSum[0]) then
     if isprime(num) then
     Begin
       cnt +=1;
       dec(nr);

       //correct changed digits in string s
       For k := dgtlen-1 downto 0 do
         s[ColWidth-k] := chr(dgtNum[k]+48);
       dgtlen := 0;

{$IFDEF DO_OUTPUT} 

       write(s);
       if nr = 0 then
       begin
         writeln;
         nr := NextRowCnt;
       end;

{$ENDIF} 

     end;
   IncNum(NumSum,1);
   end;
 if nr <>NextRowCnt then
   write(#10);
 writeln(cnt,' additive primes found.');

END. </lang>

Output:
TIO.RUN
   2   3   5   7  11  23  29  41  43  47  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449 461 463 467 487
54 additive primes found.

//OFFSET : 1000*1000*1000, RANGE = 1000*1000 no output
18103 additive primes found.
Real time: 1.951 s User time: 1.902 s Sys. time: 0.038 s CPU share: 99.46 %

Perl

Library: ntheory

<lang perl>use strict; use warnings; use ntheory 'is_prime'; use List::Util <sum max>;

sub pp { 

   my $format = ('%' . (my $cw = 1+length max @_) . 'd') x @_;
   my $width  = ".{@{[$cw * int 60/$cw]}}";
   (sprintf($format, @_)) =~ s/($width)/$1\n/gr;

}

my($limit, @ap) = 500; is_prime($_) and is_prime(sum(split ,$_)) and push @ap, $_ for 1..$limit;

print @ap . " additive primes < $limit:\n" . pp(@ap);</lang>

Output:
54 additive primes < 500:
   2   3   5   7  11  23  29  41  43  47  61  67  83  89 101
 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397
 401 409 421 443 449 461 463 467 487

Phix

function additive(integer p) return is_prime(sum(sq_sub(sprint(p),'0'))) end function
sequence res = filter(get_primes_le(500),additive)
string r = join(shorten(apply(res,sprint),"",6))
printf(1,"%d additive primes found: %s\n",{length(res),r})
Output:
54 additive primes found: 2 3 5 7 11 23 ... 443 449 461 463 467 487

PILOT

<lang pilot>C :z=2 

 :c=0
 :max=500
  • number

C :n=z U :*digsum C :n=s U :*prime J (p=0):*next C :n=z U :*prime J (p=0):*next T :#z C :c=c+1

  • next

C :z=z+1 J (z<max):*number T :There are #c additive primes below #max E :

  • prime

C :p=1 E (n<4): C :p=0 E (n=2*(n/2)): C :i=3 

 :m=n/2
  • ptest

E (n=i*(n/i)): C :i=i+2 J (i<=m):*ptest C :p=1 E :

  • digsum

C :s=0 

 :i=n
  • digit

C :j=i/10 

 :s=s+(i-j*10)
 :i=j

J (i>0):*digit E :</lang>

Output:
2
3
5
7
11
23
29
41
43
47
61
67
83
89
101
113
131
137
139
151
157
173
179
191
193
197
199
223
227
229
241
263
269
281
283
311
313
317
331
337
353
359
373
379
397
401
409
421
443
449
461
463
467
487
There are 54 additive primes below 500

PL/M

<lang plm>100H: /* FIND ADDITIVE PRIMES - PRIMES WHOSE DIGIT SUM IS ALSO PRIME */ 

   DECLARE CR LITERALLY '0DH';
   DECLARE LF LITERALLY '0AH';

   BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */
      DECLARE FN BYTE, ARG ADDRESS;
      GOTO 5;
   END BDOS;
   PRINT$CHAR:   PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
   PRINT$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
   PRINT$NL:     PROCEDURE; CALL PRINT$STRING( .( CR, LF, '$' ) ); END;
   PRINT$NUMBER: PROCEDURE( N, WIDTH );
      DECLARE N ADDRESS, WIDTH BYTE;
      DECLARE V ADDRESS, N$STR( 6 ) BYTE, ( N$POS, W ) BYTE;
      V = N; W = WIDTH + 1;
      N$STR( W ) = '$';
      N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      DO WHILE( W > 0 );
         W = W - 1;
         V = V / 10;
         IF V = 0 THEN N$STR( W ) = ' ';
                  ELSE N$STR( W ) = '0' + ( V MOD 10 );
      END;
      CALL PRINT$STRING( .N$STR( W + 1 ) );
   END PRINT$NUMBER;

   DECLARE MAX$PRIME LITERALLY '501';
   DECLARE FALSE     LITERALLY '0';
   DECLARE TRUE      LITERALLY '1';
   DECLARE PRIME( MAX$PRIME ) BYTE; /* ELEMENT 0 IS UNUSED */
   DECLARE ( A$COUNT, I, J ) ADDRESS;
   /* SIEVE THE PRIMES UP TO MAX$PRIME */
   PRIME( 1 ) = FALSE; PRIME( 2 ) = TRUE;
   DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE;  END;
   DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
   DO I = 3 TO LAST( PRIME ) / 2 BY 2;
      IF PRIME( I ) THEN DO;
         DO J = I * I TO LAST( PRIME ) BY I; PRIME( J ) = FALSE; END;
      END;
   END;
   /* FIND THE PRIMES THAT ARE ADDATIVE PRIMES */
   A$COUNT = 0;
   DO I = 1 TO LAST( PRIME );
      IF PRIME( I ) THEN DO;
         DECLARE D$SUM BYTE, V ADDRESS;
         V     = I;
         D$SUM = 0;
         DO WHILE V > 0;
            D$SUM = D$SUM + ( V MOD 10 );
            V     = V / 10;
         END;
         IF PRIME( D$SUM ) THEN DO;
            CALL PRINT$NUMBER( I, 4 );
            A$COUNT = A$COUNT + 1;
            IF A$COUNT MOD 12 = 0 THEN CALL PRINT$NL;
         END;
      END;
   END;
   CALL PRINT$NL;
   CALL PRINT$NUMBER( A$COUNT, 4 );
   CALL PRINT$STRING( .' ADDITIVE PRIMES FOUND BELOW$' );
   CALL PRINT$NUMBER( LAST( PRIME ), 4 );
   CALL PRINT$NL;

EOF </lang>

Output:
   2   3   5   7  11  23  29  41  43  47  61  67
  83  89 101 113 131 137 139 151 157 173 179 191
 193 197 199 223 227 229 241 263 269 281 283 311
 313 317 331 337 353 359 373 379 397 401 409 421
 443 449 461 463 467 487
  54 ADDITIVE PRIMES FOUND BELOW 500

Processing

<lang processing>IntList primes = new IntList();

void setup() { 

 sieve(500);
 int count = 0;
 for (int i = 2; i < 500; i++) {
   if (primes.hasValue(i) && primes.hasValue(sumDigits(i))) {
     print(i + " ");
     count++;
   }
 }
 println();
 print("Number of additive primes less than 500: " + count);

}

int sumDigits(int n) { 

 int sum = 0;
 for (int i = 0; i <= floor(log(n) / log(10)); i++) {
   sum += floor(n / pow(10, i)) % 10;
 }
 return sum;

}

void sieve(int max) { 

 for (int i = 2; i <= max; i++) {
   primes.append(i);
 }
 for (int i = 0; i < primes.size(); i++) {
   for (int j = i + 1; j < primes.size(); j++) {
     if (primes.get(j) % primes.get(i) == 0) {
       primes.remove(j);
       j--;
     }
   }
 }

}</lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 
Number of additive primes less than 500: 54

PureBasic

<lang PureBasic>#MAX=500 Global Dim P.b(#MAX) : FillMemory(@P(),#MAX,1,#PB_Byte) If OpenConsole()=0 : End 1 : EndIf For n=2 To Sqr(#MAX)+1 : If P(n) : m=n*n : While m<=#MAX : P(m)=0 : m+n : Wend : EndIf : Next

Procedure.i qsum(v.i) 

 While v : qs+v%10 : v/10 : Wend
 ProcedureReturn qs

EndProcedure

For i=2 To #MAX 

 If P(i) And P(qsum(i)) : c+1 : Print(RSet(Str(i),5)) : If c%10=0 : PrintN("") : EndIf : EndIf

Next PrintN(~"\n\n"+Str(c)+" additive primes below 500.") Input()</lang>

Output:
    2    3    5    7   11   23   29   41   43   47
   61   67   83   89  101  113  131  137  139  151
  157  173  179  191  193  197  199  223  227  229
  241  263  269  281  283  311  313  317  331  337
  353  359  373  379  397  401  409  421  443  449
  461  463  467  487

54 additive primes below 500.

Python

<lang Python>def is_prime(n: int) -> bool: 

   if n <= 3:
       return n > 1
   if n % 2 == 0 or n % 3 == 0:
       return False
   i = 5
   while i ** 2 <= n:
       if n % i == 0 or n % (i + 2) == 0:
           return False
       i += 6
   return True

def digit_sum(n: int) -> int: 

   sum = 0
   while n > 0:
       sum += n % 10
       n //= 10
   return sum

def main() -> None: 

   additive_primes = 0
   for i in range(2, 500):
       if is_prime(i) and is_prime(digit_sum(i)):
           additive_primes += 1
           print(i, end=" ")
   print(f"\nFound {additive_primes} additive primes less than 500")

if __name__ == "__main__": 

   main()</lang>
Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 
Found 54 additive primes less than 500

Quackery

eratosthenes and isprime are defined at Sieve of Eratosthenes#Quackery.

digitsum is defined at Sum digits of an integer#Quackery.

<lang Quackery> 500 eratosthenes 

 []
 500 times
   [ i^ isprime if
       [ i^ 10 digitsum 
         isprime if
           [ i^ join ] ] ] 
 dup echo cr cr
 size echo say " additive primes found."</lang>
Output:
[ 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 ]

54 additive primes found.


Raku

<lang perl6>unit sub MAIN ($limit = 500); say "{+$_} additive primes < $limit:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}", 

   with ^$limit .grep: { .is-prime and .comb.sum.is-prime }</lang>
Output:
54 additive primes < 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487

REXX

<lang rexx>/*REXX program counts/displays the number of additive primes under a specified number N.*/ parse arg n cols . /*get optional number of primes to find*/ if n== | n=="," then n= 500 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /* " " " " " */ call genP n /*generate all primes under N. */ w= 10 /*width of a number in any column. */ 

                                    title= " additive primes that are  < "     commas(n)

if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') found= 0; idx= 1 /*initialize # of additive primes & IDX*/ $= /*a list of additive primes (so far). */ 

      do j=1  for #;      p= @.j                /*obtain the  Jth  prime.              */
      _= sumDigs(p);      if \!._  then iterate /*is sum of J's digs a prime? No, skip.*/       /* ◄■■■■■■■■ a filter. */
      found= found + 1                          /*bump the count of additive primes.   */
      if cols<0                    then iterate /*Build the list  (to be shown later)? */
      c= commas(p)                              /*maybe add commas to the number.      */
      $= $  right(c, max(w, length(c) ) )       /*add additive prime──►list, allow big#*/
      if found//cols\==0           then iterate /*have we populated a line of output?  */
      say center(idx, 7)'│'  substr($, 2);  $=  /*display what we have so far  (cols). */
      idx= idx + cols                           /*bump the  index  count for the output*/
      end   /*j*/

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'found ' commas(found) title exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? sumDigs: parse arg x 1 s 2; do k=2 for length(x)-1; s= s + substr(x,k,1); end; return s /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg n; @.1= 2; @.2= 3; @.3= 5; @.4= 7; @.5= 11; @.6= 13 

                   !.= 0;   !.2= 1;  !.3= 1;  !.5= 1;  !.7= 1;  !.11= 1;  !.13= 1
                          #= 6;  sq.#= @.# ** 2 /*the number of primes;  prime squared.*/
       do j=@.#+2  by 2  for max(0, n%2-@.#%2-1)       /*find odd primes from here on. */
       parse var  j     -1  _                 /*obtain the last digit of the  J  var.*/
       if     _==5  then iterate;  if j// 3==0  then iterate  /*J ÷ by 5?   J ÷ by  3? */
       if j// 7==0  then iterate;  if j//11==0  then iterate  /*" "  " 7?   " "  " 11? */
                                                /* [↓]  divide by the primes.   ___    */
             do k=6  while sq.k<=j              /*divide  J  by other primes ≤ √ J     */
             if j//@.k==0  then iterate j       /*÷ by prev. prime?  ¬prime     ___    */
             end   /*k*/                        /* [↑]   only divide up to     √ J     */
       #= # + 1;    @.#= j;  sq.#= j*j;  !.j= 1 /*bump prime count; assign prime & flag*/
       end   /*j*/;                      return</lang>
output   when using the default inputs:
 index │                                        additive primes that are  <  500
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2          3          5          7         11         23         29         41         43         47
  11   │         61         67         83         89        101        113        131        137        139        151
  21   │        157        173        179        191        193        197        199        223        227        229
  31   │        241        263        269        281        283        311        313        317        331        337
  41   │        353        359        373        379        397        401        409        421        443        449
  51   │        461        463        467        487
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────

found  54  additive primes that are  <  500

Ring

<lang ring> load "stdlib.ring"

see "working..." + nl see "Additive primes are:" + nl

row = 0 limit = 500

for n = 1 to limit 

   num = 0
   if isprime(n) 
      strn = string(n)
      for m = 1 to len(strn)
          num = num + number(strn[m])
      next
      if isprime(num)
         row = row + 1
         see "" + n + " "
         if row%10 = 0
            see nl
         ok
      ok
   ok

next

see nl + "found " + row + " additive primes." + nl see "done..." + nl </lang>

Output:
working...
Additive primes are:
2 3 5 7 11 23 29 41 43 47 
61 67 83 89 101 113 131 137 139 151 
157 173 179 191 193 197 199 223 227 229 
241 263 269 281 283 311 313 317 331 337 
353 359 373 379 397 401 409 421 443 449 
461 463 467 487 
found 54 additive primes.
done...

Ruby

<lang ruby>require "prime"

additive_primes = Prime.lazy.select{|prime| prime.digits.sum.prime? }

N = 500 res = additive_primes.take_while{|n| n < N}.to_a puts res.join(" ") puts "\n#{res.size} additive primes below #{N}." </lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487

54 additive primes below 500.


Rust

Flat implementation

<lang Rust> fn main() { 

   let limit = 500;
   //all primes, starting from 3 (including non-additive), will be collected in pms
   //  it works ~1.5 times faster than the variant with fn is_prime(){...while...+=6...}
   let mut pms = Vec::with_capacity(limit / 2 - limit / 3 / 2 - limit / 5 / 3 / 2 + 1);
   let column_width = limit.to_string().len() + 1;
   print!("{:1$}", 2, column_width);
   let mut count = 1;
   for u in (3..limit).step_by(2) {
       if pms.iter().take_while(|&&p| p * p <= u).all(|&p| u % p != 0) {
           pms.push(u);
           //about the same speed as while...{...+=...%.../=...}, but without mut
           let sum_digits = std::iter::successors(Some(u), |&n| (n > 9).then(|| n / 10))
               .fold(0, |s, n| s + n % 10);
           if sum_digits == 2 || matches!(pms.binary_search(&sum_digits), Ok(_)) {
               if count % 10 == 0 {
                   print!("\n");
               }
               print!("{:1$}", u, column_width);
               count += 1;
           }
       }
   }
   println!("\n---\nFound {} additive primes less than {}", count, limit);

} </lang>

Output:
   2   3   5   7  11  23  29  41  43  47
  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449
 461 463 467 487
---
Found 54 additive primes less than 500


With crate "primal"

primal implements the sieve of Eratosthenes with optimizations (10+ times faster for large limits)

<lang Rust> // [dependencies] // primal = "0.3.0"

use primal::Sieve;

fn main() { 

   let limit = 500;
   let column_width = limit.to_string().len() + 1;
   let sieve_primes = Sieve::new(limit);
   let mut count = 0;
   for u in sieve_primes.primes_from(2).filter(|&p| {
       p < limit
           && sieve_primes.is_prime(
               std::iter::successors(Some(p), |&n| (n > 9).then(|| n / 10))
                   .fold(0, |s, n| s + n % 10),
           )
   }) {
       if count % 10 == 0 {
           println!();
       }
       print!("{:1$}", u, column_width);
       count += 1;
   }
   println!("\n---\nFound {} additive primes less than {}", count, limit);

} </lang>

Output:
   2   3   5   7  11  23  29  41  43  47
  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449
 461 463 467 487
---
Found 54 additive primes less than 500

Sage

<lang SageMath> limit = 500 additivePrimes = list(filter(lambda x: x > 0, 

                            list(map(lambda x: int(x) if sum([int(digit) for digit in x]) in Primes() else 0, 
                                     list(map(str,list(primes(1,limit))))))))

print(f"{additivePrimes}\nFound {len(additivePrimes)} additive primes less than {limit}") </lang>

Output:
[2, 3, 5, 7, 11, 23, 29, 41, 43, 47, 61, 67, 83, 89, 101, 113, 131, 137, 139, 151, 157, 173, 179, 191, 193, 197, 199, 223, 227, 229, 241, 263, 269, 281, 283, 311, 313, 317, 331, 337, 353, 359, 373, 379, 397, 401, 409, 421, 443, 449, 461, 463, 467, 487]
Found 54 additive primes less than 500

Seed7

<lang seed7>$ include "seed7_05.s7i";

const func boolean: isPrime (in integer: number) is func 

 result
   var boolean: prime is FALSE;
 local
   var integer: upTo is 0;
   var integer: testNum is 3;
 begin
   if number = 2 then
     prime := TRUE;
   elsif odd(number) and number > 2 then
     upTo := sqrt(number);
     while number rem testNum <> 0 and testNum <= upTo do
       testNum +:= 2;
     end while;
     prime := testNum > upTo;
   end if;
 end func;

const func integer: digitSum (in var integer: number) is func 

 result
   var integer: sum is 0;
 begin
   while number > 0 do
     sum +:= number rem 10;
     number := number div 10;
   end while;
 end func;

const proc: main is func 

 local
   var integer: n is 0;
   var integer: count is 0;
 begin
   for n range 2 to 499 do
     if isPrime(n) and isPrime(digitSum(n)) then
       write(n lpad 3 <& " ");
       incr(count);
       if count rem 9 = 0 then
         writeln;
       end if;
     end if;
   end for;
   writeln("\nFound " <& count <& " additive primes < 500.");
 end func;</lang>
Output:
  2   3   5   7  11  23  29  41  43
 47  61  67  83  89 101 113 131 137
139 151 157 173 179 191 193 197 199
223 227 229 241 263 269 281 283 311
313 317 331 337 353 359 373 379 397
401 409 421 443 449 461 463 467 487

Found 54 additive primes < 500.

Sidef

<lang ruby>func additive_primes(upto, base = 10) { 

   upto.primes.grep { .sumdigits(base).is_prime }

}

additive_primes(500).each_slice(10, {|*a| 

   a.map { '%3s' % _ }.join(' ').say

})</lang>

Output:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487

Swift

<lang swift>import Foundation

func isPrime(_ n: Int) -> Bool { 

   if n < 2 {
       return false
   }
   if n % 2 == 0 {
       return n == 2
   }
   if n % 3 == 0 {
       return n == 3
   }
   var p = 5
   while p * p <= n {
       if n % p == 0 {
           return false
       }
       p += 2
       if n % p == 0 {
           return false
       }
       p += 4
   }
   return true

}

func digitSum(_ num: Int) -> Int { 

   var sum = 0
   var n = num
   while n > 0 {
       sum += n % 10
       n /= 10
   }
   return sum

}

let limit = 500 print("Additive primes less than \(limit):") var count = 0 for n in 1..<limit { 

   if isPrime(digitSum(n)) && isPrime(n) {
       count += 1
       print(String(format: "%3d", n), terminator: count % 10 == 0 ? "\n" : " ")
   }

} print("\n\(count) additive primes found.")</lang>

Output:
Additive primes less than 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487 
54 additive primes found.

Wren

Library: Wren-math
Library: Wren-fmt

<lang ecmascript>import "/math" for Int import "/fmt" for Fmt

var sumDigits = Fn.new { |n| 

   var sum = 0
   while (n > 0) {
       sum = sum + (n % 10)
       n = (n/10).floor
   }
   return sum

}

System.print("Additive primes less than 500:") var primes = Int.primeSieve(499) var count = 0 for (p in primes) { 

   if (Int.isPrime(sumDigits.call(p))) {
       count = count + 1
       Fmt.write("$3d  ", p)
       if (count % 10 == 0) System.print()
   }

} System.print("\n\n%(count) additive primes found.")</lang>

Output:
Additive primes less than 500:
  2    3    5    7   11   23   29   41   43   47  
 61   67   83   89  101  113  131  137  139  151  
157  173  179  191  193  197  199  223  227  229  
241  263  269  281  283  311  313  317  331  337  
353  359  373  379  397  401  409  421  443  449  
461  463  467  487  

54 additive primes found.

XPL0

<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do 

   if rem(N/I) = 0 then return false;

return true; ];

func SumDigits(N); \Return the sum of the digits in N int N, Sum; [Sum:= 0; repeat N:= N/10; 

       Sum:= Sum + rem(0);

until N=0; return Sum; ];

int Count, N; [Count:= 0; for N:= 0 to 500-1 do 

   if IsPrime(N) & IsPrime(SumDigits(N)) then
       [IntOut(0, N);
       Count:= Count+1;
       if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
       ];

CrLf(0); IntOut(0, Count); Text(0, " additive primes found below 500. "); ]</lang>

Output:
2       3       5       7       11      23      29      41      43      47
61      67      83      89      101     113     131     137     139     151
157     173     179     191     193     197     199     223     227     229
241     263     269     281     283     311     313     317     331     337
353     359     373     379     397     401     409     421     443     449
461     463     467     487     
54 additive primes found below 500.
Retrieved from "https://rosettacode.org/wiki/Additive_primes?oldid=309809"