Additive primes
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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
-
- the OEIS entry: A046704 additive primes.
- the prime-numbers entry: additive primes.
- the geeks for geeks entry: additive prime number.
- the prime-numbers fandom: additive primes.
11l
<lang 11l>F is_prime(a)
I a == 2 R 1B I a < 2 | a % 2 == 0 R 0B L(i) (3 .. Int(sqrt(a))).step(2) I a % i == 0 R 0B R 1B
F digit_sum(=n)
V sum = 0 L n > 0 sum += n % 10 n I/= 10 R sum
V additive_primes = 0 L(i) 2..499
I is_prime(i) & is_prime(digit_sum(i)) additive_primes++ print(i, end' ‘ ’)
print("\nFound "additive_primes‘ 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
AArch64 Assembly
<lang AArch64 Assembly> /* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */ /* program additivePrime64.s */
/*******************************************/ /* Constantes file */ /*******************************************/ /* for this file see task include a file in language AArch64 assembly*/ .include "../includeConstantesARM64.inc"
.equ MAXI, 500
/*********************************/ /* Initialized data */ /*********************************/ .data szMessResult: .asciz "Prime : @ \n" szMessCounter: .asciz "Number found : @ \n" szCarriageReturn: .asciz "\n"
/*********************************/ /* UnInitialized data */ /*********************************/ .bss sZoneConv: .skip 24 TablePrime: .skip 8 * MAXI /*********************************/ /* code section */ /*********************************/ .text .global main main: // entry of program
bl createArrayPrime mov x5,x0 // prime number
ldr x4,qAdrTablePrime // address prime table mov x10,#0 // init counter mov x6,#0 // indice
1:
ldr x2,[x4,x6,lsl #3] // load prime mov x9,x2 // save prime mov x7,#0 // init digit sum mov x1,#10 // divisor
2: // begin loop
mov x0,x2 // dividende udiv x2,x0,x1 msub x3,x2,x1,x0 // compute remainder add x7,x7,x3 // add digit to digit sum cmp x2,#0 // quotient null ? bne 2b // no -> comppute other digit
mov x8,#1 // indice
4: // prime search loop
cmp x8,x5 // maxi ? bge 5f // yes ldr x0,[x4,x8,lsl #3] // load prime cmp x0,x7 // prime >= digit sum ? add x0,x8,1 csel x8,x0,x8,lt // no -> increment indice blt 4b // and loop bne 5f // > mov x0,x9 // equal bl displayPrime add x10,x10,#1 // increment counter
5:
add x6,x6,#1 // increment first indice cmp x6,x5 // maxi ? blt 1b // and loop mov x0,x10 // number counter ldr x1,qAdrsZoneConv bl conversion10 // call décimal conversion ldr x0,qAdrszMessCounter ldr x1,qAdrsZoneConv // insert conversion in message bl strInsertAtCharInc bl affichageMess // display message
100: // standard end of the program
mov x0, #0 // return code mov x8, #EXIT // request to exit program svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn qAdrszMessResult: .quad szMessResult qAdrszMessCounter: .quad szMessCounter qAdrTablePrime: .quad TablePrime /******************************************************************/ /* créate prime array */ /******************************************************************/ createArrayPrime:
stp x1,lr,[sp,-16]! // save registres ldr x4,qAdrTablePrime // address prime table mov x0,#1 str x0,[x4] // store 1 in array mov x0,#2 str x0,[x4,#8] // store 2 in array mov x0,#3 str x0,[x4,#16] // store 3 in array mov x5,#3 // prine counter mov x7,#5 // first number to test
1:
mov x6,#1 // indice
2:
mov x0,x7 // dividende ldr x1,[x4,x6,lsl #3] // load divisor udiv x2,x0,x1 msub x3,x2,x1,x0 // compute remainder cmp x3,#0 // null remainder ? beq 4f // yes -> end loop cmp x2,x1 // quotient < divisor bge 3f str x7,[x4,x5,lsl #3] // dividende is prime store in array add x5,x5,#1 // increment counter b 4f // and end loop
3:
add x6,x6,#1 // else increment indice cmp x6,x5 // maxi ? blt 2b // no -> loop
4:
add x7,x7,#2 // other odd number cmp x7,#MAXI // maxi ? blt 1b // no -> loop mov x0,x5 // return counter
100:
ldp x1,lr,[sp],16 // restaur des 2 registres ret
/******************************************************************/ /* Display prime table elements */ /******************************************************************/ /* x0 contains the prime */ displayPrime:
stp x1,lr,[sp,-16]! // save registres ldr x1,qAdrsZoneConv bl conversion10 // call décimal conversion ldr x0,qAdrszMessResult ldr x1,qAdrsZoneConv // insert conversion in message bl strInsertAtCharInc bl affichageMess // display message
100:
ldp x1,lr,[sp],16 // restaur des 2 registres ret
qAdrsZoneConv: .quad sZoneConv
/********************************************************/ /* File Include fonctions */ /********************************************************/ /* for this file see task include a file in language AArch64 assembly */ .include "../includeARM64.inc"
</lang>
Prime : 2 Prime : 3 Prime : 5 Prime : 7 Prime : 11 Prime : 23 Prime : 29 Prime : 41 Prime : 43 Prime : 47 Prime : 61 Prime : 67 Prime : 83 Prime : 89 Prime : 101 Prime : 113 Prime : 131 Prime : 137 Prime : 139 Prime : 151 Prime : 157 Prime : 173 Prime : 179 Prime : 191 Prime : 193 Prime : 197 Prime : 199 Prime : 223 Prime : 227 Prime : 229 Prime : 241 Prime : 263 Prime : 269 Prime : 281 Prime : 283 Prime : 311 Prime : 313 Prime : 317 Prime : 331 Prime : 337 Prime : 353 Prime : 359 Prime : 373 Prime : 379 Prime : 397 Prime : 401 Prime : 409 Prime : 421 Prime : 443 Prime : 449 Prime : 461 Prime : 463 Prime : 467 Prime : 487 Number found : 54
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
<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>
ARM Assembly
<lang ARM Assembly> /* ARM assembly Raspberry PI */ /* program additivePrime.s */
/* REMARK 1 : this program use routines in a include file see task Include a file language arm assembly for the routine affichageMess conversion10 see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */ /************************************/ /* Constantes */ /************************************/ .include "../constantes.inc"
.equ MAXI, 500
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Prime : @ \n"
szMessCounter: .asciz "Number found : @ \n"
szCarriageReturn: .asciz "\n"
/*********************************/ /* UnInitialized data */ /*********************************/ .bss sZoneConv: .skip 24 TablePrime: .skip 4 * MAXI /*********************************/ /* code section */ /*********************************/ .text .global main main: @ entry of program
bl createArrayPrime mov r5,r0 @ prime number
ldr r4,iAdrTablePrime @ address prime table mov r10,#0 @ init counter mov r6,#0 @ indice
1:
ldr r2,[r4,r6,lsl #2] @ load prime mov r9,r2 @ save prime mov r7,#0 @ init digit sum mov r1,#10 @ divisor
2: @ begin loop
mov r0,r2 @ dividende bl division add r7,r7,r3 @ add digit to digit sum cmp r2,#0 @ quotient null ? bne 2b @ no -> comppute other digit
mov r8,#1 @ indice
4: @ prime search loop
cmp r8,r5 @ maxi ? bge 5f @ yes ldr r0,[r4,r8,lsl #2] @ load prime cmp r0,r7 @ prime >= digit sum ? addlt r8,r8,#1 @ no -> increment indice blt 4b @ and loop bne 5f @ > mov r0,r9 @ equal bl displayPrime add r10,r10,#1 @ increment counter
5:
add r6,r6,#1 @ increment first indice cmp r6,r5 @ maxi ? blt 1b @ and loop mov r0,r10 @ number counter ldr r1,iAdrsZoneConv bl conversion10 @ call décimal conversion ldr r0,iAdrszMessCounter ldr r1,iAdrsZoneConv @ insert conversion in message bl strInsertAtCharInc bl affichageMess @ display message
100: @ standard end of the program
mov r0, #0 @ return code mov r7, #EXIT @ request to exit program svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn iAdrszMessResult: .int szMessResult iAdrszMessCounter: .int szMessCounter iAdrTablePrime: .int TablePrime /******************************************************************/ /* créate prime array */ /******************************************************************/ createArrayPrime:
push {r1-r7,lr} @ save registers ldr r4,iAdrTablePrime @ address prime table mov r0,#1 str r0,[r4] @ store 1 in array mov r0,#2 str r0,[r4,#4] @ store 2 in array mov r0,#3 str r0,[r4,#8] @ store 3 in array mov r5,#3 @ prine counter mov r7,#5 @ first number to test
1:
mov r6,#1 @ indice
2:
mov r0,r7 @ dividende ldr r1,[r4,r6,lsl #2] @ load divisor bl division cmp r3,#0 @ null remainder ? beq 3f @ yes -> end loop cmp r2,r1 @ quotient < divisor strlt r7,[r4,r5,lsl #2] @ dividende is prime store in array addlt r5,r5,#1 @ increment counter blt 3f @ and end loop add r6,r6,#1 @ else increment indice cmp r6,r5 @ maxi ? blt 2b @ no -> loop
3:
add r7,#2 @ other odd number cmp r7,#MAXI @ maxi ? blt 1b @ no -> loop mov r0,r5 @ return counter
100:
pop {r1-r7,pc}
/******************************************************************/ /* Display prime table elements */ /******************************************************************/ /* r0 contains the prime */ displayPrime:
push {r1,lr} @ save registers ldr r1,iAdrsZoneConv bl conversion10 @ call décimal conversion ldr r0,iAdrszMessResult ldr r1,iAdrsZoneConv @ insert conversion in message bl strInsertAtCharInc bl affichageMess @ display message
100:
pop {r1,pc}
iAdrsZoneConv: .int sZoneConv /***************************************************/ /* ROUTINES INCLUDE */ /***************************************************/ .include "../affichage.inc"
</lang>
Prime : 2 Prime : 3 Prime : 5 Prime : 7 Prime : 11 Prime : 23 Prime : 29 Prime : 41 Prime : 43 Prime : 47 Prime : 61 Prime : 67 Prime : 83 Prime : 89 Prime : 101 Prime : 113 Prime : 131 Prime : 137 Prime : 139 Prime : 151 Prime : 157 Prime : 173 Prime : 179 Prime : 191 Prime : 193 Prime : 197 Prime : 199 Prime : 223 Prime : 227 Prime : 229 Prime : 241 Prime : 263 Prime : 269 Prime : 281 Prime : 283 Prime : 311 Prime : 313 Prime : 317 Prime : 331 Prime : 337 Prime : 353 Prime : 359 Prime : 373 Prime : 379 Prime : 397 Prime : 401 Prime : 409 Prime : 421 Prime : 443 Prime : 449 Prime : 461 Prime : 463 Prime : 467 Prime : 487 Number found : 54
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>
- 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>
- include <stdbool.h>
- include <stdio.h>
- 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>
- 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.
CLU
<lang clu>% Sieve of Erastothenes % Returns an array [1..max] marking the primes sieve = proc (max: int) returns (array[bool])
prime: array[bool] := array[bool]$fill(1, max, true) prime[1] := false for p: int in int$from_to(2, max/2) do if prime[p] then for comp: int in int$from_to_by(p*2, max, p) do prime[comp] := false end end end return(prime)
end sieve
% Sum the digits of a number digit_sum = proc (n: int) returns (int)
sum: int := 0 while n ~= 0 do sum := sum + n // 10 n := n / 10 end return(sum)
end digit_sum
start_up = proc ()
max = 500 po: stream := stream$primary_output() count: int := 0 prime: array[bool] := sieve(max) for i: int in array[bool]$indexes(prime) do if prime[i] cand prime[digit_sum(i)] then count := count + 1 stream$putright(po, int$unparse(i), 5) if count//10 = 0 then stream$putl(po, "") end end end stream$putl(po, "\nFound " || int$unparse(count) || " additive primes < " || int$unparse(max))
end start_up</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
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
Crystal
<lang ruby># Fast/simple way to generate primes for small values.
- Uses P3 Prime Generator (PG) and its Prime Generator Sequence (PGS).
def prime?(n) # P3 Prime Generator primality test
return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5 sqrt_n = Math.isqrt(n) # For Crystal < 1.2.0 use Math.sqrt(n).to_i pc = typeof(n).new(5) while pc <= sqrt_n return false if n % pc == 0 || n % (pc + 2) == 0 pc += 6 end true
end
def additive_primes(n)
primes = [2, 3] pc, inc = 5, 2 while pc < n primes << pc if prime?(pc) && prime?(pc.digits.sum) pc += inc; inc ^= 0b110 # generate P3 sequence: 5 7 11 13 17 19 ... end primes # list of additive primes <= n
end
nn = 500 addprimes = additive_primes(nn) maxdigits = addprimes.last.digits.size addprimes.each_with_index { |n, idx| printf "%*d ", maxdigits, n; print "\n" if idx % 10 == 9 } # more efficient
- addprimes.each_with_index { |n, idx| print "%#{maxdigits}d " % n; print "\n" if idx % 10 == 9} # alternatively
puts "\n#{addprimes.size} additive primes below #{nn}."
puts
nn = 5000 addprimes = additive_primes(nn) maxdigits = addprimes.last.digits.size addprimes.each_with_index { |n, idx| printf "%*d ", maxdigits, n; print "\n" if idx % 10 == 9 } # more efficient puts "\n#{addprimes.size} additive primes below #{nn}." </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. 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 557 571 577 593 599 601 607 641 643 647 661 683 719 733 739 751 757 773 797 809 821 823 827 829 863 881 883 887 911 919 937 953 971 977 991 1013 1019 1031 1033 1039 1051 1091 1093 1097 1103 1109 1123 1129 1163 1181 1187 1213 1217 1231 1237 1259 1277 1279 1291 1297 1301 1303 1307 1321 1327 1361 1367 1381 1433 1439 1451 1453 1459 1471 1493 1499 1523 1543 1549 1567 1583 1613 1619 1637 1657 1693 1697 1709 1721 1723 1741 1747 1783 1787 1811 1831 1871 1873 1877 1901 1907 1949 2003 2027 2029 2063 2069 2081 2083 2087 2089 2111 2113 2131 2137 2153 2179 2203 2207 2221 2243 2267 2269 2281 2287 2311 2333 2339 2351 2357 2371 2377 2393 2399 2423 2441 2447 2467 2531 2539 2551 2557 2579 2591 2593 2609 2621 2647 2663 2683 2687 2711 2713 2719 2731 2753 2777 2791 2801 2803 2843 2861 2917 2939 2953 2957 2971 2999 3011 3019 3037 3079 3109 3121 3163 3167 3169 3181 3187 3217 3251 3253 3257 3259 3271 3299 3301 3307 3323 3329 3343 3347 3361 3389 3413 3433 3457 3491 3527 3529 3541 3547 3581 3583 3613 3617 3631 3637 3659 3671 3673 3677 3691 3701 3709 3727 3761 3767 3833 3851 3853 3907 3923 3929 3943 3947 3989 4001 4003 4007 4021 4027 4049 4111 4133 4139 4153 4157 4159 4177 4201 4229 4241 4243 4261 4283 4289 4337 4339 4357 4373 4391 4397 4409 4421 4423 4441 4447 4463 4481 4483 4513 4517 4519 4591 4603 4621 4643 4649 4663 4733 4751 4793 4799 4801 4861 4889 4919 4931 4933 4937 4951 4973 4999 338 additive primes below 5000.
Delphi
See Pascal.
Erlang
<lang Erlang> main(_) ->
AddPrimes = [N || N <- lists:seq(2,500), isprime(N) andalso isprime(digitsum(N))], io:format("The additive primes up to 500 are:~n~p~n~n", [AddPrimes]), io:format("There are ~b of them.~n", [length(AddPrimes)]).
isprime(N) when N < 2 -> false; isprime(N) -> isprime(N, 2, 0, <<1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6>>).
isprime(N, D, J, Wheel) when J =:= byte_size(Wheel) -> isprime(N, D, 3, Wheel); isprime(N, D, _, _) when D*D > N -> true; isprime(N, D, _, _) when N rem D =:= 0 -> false; isprime(N, D, J, Wheel) -> isprime(N, D + binary:at(Wheel, J), J + 1, Wheel).
digitsum(N) -> digitsum(N, 0). digitsum(0, S) -> S; digitsum(N, S) -> digitsum(N div 10, S + N rem 10). </lang>
- Output:
The additive primes up to 500 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] There are 54 of them.
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
<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 -> 19There were 54
Forth
<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.
J
<lang J> (#~ 1 p: [:+/@|: 10&#.inv) i.&.(p:inv) 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</lang>
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 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;
- 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);
- 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>
- Input: a number n
- 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
<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
- Prime numbers for which the sum of their decimal digits are also primes
- # Variables:
integer MAX_n=500
- # Functions:
- # 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 }
- # 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} }
######
- 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</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
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
- 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
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;//
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 := p + wheeldiff[flipflop]; if p * p > n then BREAK; result := n mod p <> 0; flipflop := 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 := num + delta; repeat carry := delta div BASE; delta := delta - BASE * carry; dg := dgtNum[le] + delta; IF dg >= BASE then Begin dg := 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 := delta + dgtNum[le]; dgtSum[le] := delta; until le = 0; end;
end;
var
NumSum: tNumSum; s: AnsiString; i, k, cnt, Nr: NativeUInt; ColWidth, MAXCOLUMNS, NextRowCnt: NativeUInt;
BEGIN
ColWidth := Trunc(ln(MAX_OFFSET + RANGE) / ln(10)) + 2; MAXCOLUMNS := 80; NextRowCnt := MAXCOLUMNS DIV ColWidth;
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] := AnsiChar(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 := cnt + 1; dec(Nr);
// correct changed digits in string s For k := dgtLen - 1 downto 0 do s[ColWidth - k] := AnsiChar(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
<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
with javascript_semantics function additive(string p) return is_prime(sum(sq_sub(p,'0'))) end function sequence res = filter(apply(get_primes_le(500),sprint),additive) printf(1,"%d additive primes found: %s\n",{length(res),join(shorten(res,"",6))})
- Output:
54 additive primes found: 2 3 5 7 11 23 ... 443 449 461 463 467 487
PicoLisp
<lang PicoLisp>(de prime? (N)
(let D 0 (or (= N 2) (and (> N 1) (bit? 1 N) (for (D 3 T (+ D 2)) (T (> D (sqrt N)) T) (T (=0 (% N D)) NIL) ) ) ) ) )
(de additive (N)
(and (prime? N) (prime? (sum format (chop N))) ) )
(let C 0
(for (N 0 (> 500 N) (inc N)) (when (additive N) (printsp N) (inc 'C) ) ) (prinl) (prinl "Total count: " C) )</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 Total count: 54
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/I
PL/M
Polyglot:PL/I and PL/M
... under CP/M (or an emulator)
Should work with many PL/I implementations.
The PL/I include file "pg.inc" can be found on the Polyglot:PL/I and PL/M page.
Note the use of text in column 81 onwards to hide the PL/I specifics from the PL/M compiler.
<lang pli>/* FIND ADDITIVE PRIMES - PRIMES WHOSE DIGIT SUM IS ALSO PRIME */
additive_primes_100H: procedure options (main);
/* PROGRAM-SPECIFIC %REPLACE STATEMENTS MUST APPEAR BEFORE THE %INCLUDE AS */ /* E.G. THE CP/M PL/I COMPILER DOESN'T LIKE THEM TO FOLLOW PROCEDURES */
/* PL/I */ %replace dclsieve by 500; /* PL/M */ /* DECLARE DCLSIEVE LITERALLY '501'; /* */
/* PL/I DEFINITIONS */ %include 'pg.inc'; /* PL/M DEFINITIONS: CP/M BDOS SYSTEM CALL AND CONSOLE I/O ROUTINES, ETC. */ /*
DECLARE BINARY LITERALLY 'ADDRESS', CHARACTER LITERALLY 'BYTE'; DECLARE FIXED LITERALLY ' ', BIT LITERALLY 'BYTE'; DECLARE STATIC LITERALLY ' ', RETURNS LITERALLY ' '; DECLARE FALSE LITERALLY '0', TRUE LITERALLY '1'; DECLARE HBOUND LITERALLY 'LAST', SADDR LITERALLY '.'; BDOSF: PROCEDURE( FN, ARG )BYTE; DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END; BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END; PRCHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END; PRSTRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END; PRNL: PROCEDURE; CALL PRCHAR( 0DH ); CALL PRCHAR( 0AH ); END; PRNUMBER: PROCEDURE( N ); DECLARE N ADDRESS; DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE; N$STR( W := LAST( N$STR ) ) = '$'; N$STR( W := W - 1 ) = '0' + ( ( V := N ) MOD 10 ); DO WHILE( ( V := V / 10 ) > 0 ); N$STR( W := W - 1 ) = '0' + ( V MOD 10 ); END; CALL BDOS( 9, .N$STR( W ) ); END PRNUMBER; MODF: PROCEDURE( A, B )ADDRESS; DECLARE ( A, B ) ADDRESS; RETURN A MOD B; END MODF;
/* END LANGUAGE DEFINITIONS */
/* TASK */
/* PRIME ELEMENTS ARE 0, 1, ... 500 IN PL/M AND 1, 2, ... 500 IN PL/I */ /* ELEMENT 0 IN PL/M IS IS UNUSED */ DECLARE PRIME( DCLSIEVE ) BIT; DECLARE ( MAXPRIME, MAXROOT, ACOUNT, I, J, DSUM, V ) FIXED BINARY; /* SIEVE THE PRIMES UP TO MAX PRIME */ PRIME( 1 ) = FALSE; PRIME( 2 ) = TRUE; MAXPRIME = HBOUND( PRIME , 1 ); MAXROOT = 1; /* FIND THE ROOT OF MAXPRIME TO AVOID 16-BIT OVERFLOW */ DO WHILE( MAXROOT * MAXROOT < MAXPRIME ); MAXROOT = MAXROOT + 1; END; DO I = 3 TO MAXPRIME BY 2; PRIME( I ) = TRUE; END; DO I = 4 TO MAXPRIME BY 2; PRIME( I ) = FALSE; END; DO I = 3 TO MAXROOT BY 2; IF PRIME( I ) THEN DO; DO J = I * I TO MAXPRIME BY I; PRIME( J ) = FALSE; END; END; END; /* FIND THE PRIMES THAT ARE ADDITIVE PRIMES */ ACOUNT = 0; DO I = 1 TO MAXPRIME; IF PRIME( I ) THEN DO; V = I; DSUM = 0; DO WHILE( V > 0 ); DSUM = DSUM + MODF( V, 10 ); V = V / 10; END; IF PRIME( DSUM ) THEN DO; CALL PRCHAR( ' ' ); IF I < 10 THEN CALL PRCHAR( ' ' ); IF I < 100 THEN CALL PRCHAR( ' ' ); CALL PRNUMBER( I ); ACOUNT = ACOUNT + 1; IF MODF( ACOUNT, 12 ) = 0 THEN CALL PRNL; END; END; END; CALL PRNL; CALL PRSTRING( SADDR( 'FOUND $' ) ); CALL PRNUMBER( ACOUNT ); CALL PRSTRING( SADDR( ' ADDITIVE PRIMES BELOW $' ) ); CALL PRNUMBER( MAXPRIME ); CALL PRNL;
EOF: end additive_primes_100H;</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
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.
Racket
<lang racket>#lang racket
(require math/number-theory)
(define (sum-of-digits n (σ 0))
(if (zero? n) σ (let-values (((q r) (quotient/remainder n 10))) (sum-of-digits q (+ σ r)))))
(define (additive-prime? n)
(and (prime? n) (prime? (sum-of-digits n))))
(define additive-primes<500 (filter additive-prime? (range 1 500))) (printf "There are ~a additive primes < 500~%" (length additive-primes<500)) (printf "They are: ~a~%" additive-primes<500)</lang>
- Output:
There are 54 additive primes < 500 They 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)
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
Red
<lang Red> cross-sum: function [n][out: 0 foreach m form n [out: out + to-integer to-string m]] additive-primes: function [n][collect [foreach p ps: primes n [if find ps cross-sum p [keep p]]]]
length? probe new-line/skip additive-primes 500 true 10 [
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
</lang>
Uses primes
defined in https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Red.
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 fsharp>fn main() {
let limit = 500; let column_w = limit.to_string().len() + 1; let mut pms = Vec::with_capacity(limit / 2 - limit / 3 / 2 - limit / 5 / 3 / 2 + 1); let mut count = 0; for u in (2..3).chain((3..limit).step_by(2)) { if pms.iter().take_while(|&&p| p * p <= u).all(|&p| u % p != 0) { pms.push(u); let dgs = std::iter::successors(Some(u), |&n| (n > 9).then(|| n / 10)).map(|n| n % 10); if pms.binary_search(&dgs.sum()).is_ok() { print!("{}{u:column_w$}", if count % 10 == 0 { "\n" } else { "" }); count += 1; } } } println!("\n---\nFound {count} 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
With crate "primal"
primal implements the sieve of Eratosthenes with optimizations (10+ times faster for large limits)
<lang fsharp>// [dependencies] // primal = "0.3.0"
fn sum_digits(u: usize) -> usize {
std::iter::successors(Some(u), |&n| (n > 9).then(|| n / 10)).fold(0, |s, n| s + n % 10)
}
fn main() {
let limit = 500; let column_w = limit.to_string().len() + 1; let sieve_primes = primal::Sieve::new(limit); let count = sieve_primes .primes_from(2) .filter(|&p| p < limit && sieve_primes.is_prime(sum_digits(p))) .zip(["\n"].iter().chain(&[""; 9]).cycle()) .inspect(|(u, sn)| print!("{sn}{u:column_w$}")) .count(); println!("\n---\nFound {count} 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
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
TSE SAL
<lang TSESAL>
INTEGER PROC FNMathGetSquareRootI( INTEGER xI )
INTEGER squareRootI = 0 IF ( xI > 0 ) WHILE( ( squareRootI * squareRootI ) <= xI ) squareRootI = squareRootI + 1 ENDWHILE squareRootI = squareRootI - 1 ENDIF RETURN( squareRootI )
END // INTEGER PROC FNMathCheckIntegerIsPrimeB( INTEGER nI )
INTEGER I = 0 INTEGER primeB = FALSE INTEGER stopB = FALSE INTEGER restI = 0 INTEGER limitI = 0 primeB = FALSE IF ( nI <= 0 ) RETURN( FALSE ) ENDIF IF ( nI == 1 ) RETURN( FALSE ) ENDIF IF ( nI == 2 ) RETURN( TRUE ) ENDIF IF ( nI == 3 ) RETURN( TRUE ) ENDIF IF ( nI MOD 2 == 0 ) RETURN( FALSE ) ENDIF IF ( ( nI MOD 6 ) <> 1 ) AND ( ( nI MOD 6 ) <> 5 ) RETURN( FALSE ) ENDIF limitI = FNMathGetSquareRootI( nI ) I = 3 REPEAT restI = ( nI MOD I ) IF ( restI == 0 ) primeB = FALSE stopB = TRUE ENDIF IF ( I > limitI ) primeB = TRUE stopB = TRUE ENDIF I = I + 2 UNTIL ( stopB ) RETURN( primeB )
END // INTEGER PROC FNMathCheckIntegerDigitSumI( INTEGER J )
STRING s[255] = Str( J ) STRING cS[255] = "" INTEGER minI = 1 INTEGER maxI = Length( s ) INTEGER I = 0 INTEGER K = 0 FOR I = minI TO maxI cS = s[ I ] K = K + Val( cS ) ENDFOR RETURN( K )
END // INTEGER PROC FNMathCheckIntegerDigitSumIsPrimeB( INTEGER I )
INTEGER J = FNMathCheckIntegerDigitSumI( I ) INTEGER B = FNMathCheckIntegerIsPrimeB( J ) RETURN( B )
END // INTEGER PROC FNMathGetPrimeAdditiveAllToBufferB( INTEGER maxI, INTEGER bufferI )
INTEGER B = FALSE INTEGER B1 = FALSE INTEGER B2 = FALSE INTEGER B3 = FALSE INTEGER minI = 2 INTEGER I = 0 FOR I = minI TO maxI B1 = FNMathCheckIntegerIsPrimeB( I ) B2 = FNMathCheckIntegerDigitSumIsPrimeB( I ) B3 = B1 AND B2 IF ( B3 ) PushPosition() PushBlock() GotoBufferId( bufferI ) AddLine( Str( I ) ) PopBlock() PopPosition() ENDIF ENDFOR B = TRUE RETURN( B )
END // PROC Main()
STRING s1[255] = "500" // change this INTEGER bufferI = 0 PushPosition() bufferI = CreateTempBuffer() PopPosition() IF ( NOT ( Ask( " = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF Message( FNMathGetPrimeAdditiveAllToBufferB( Val( s1 ), bufferI ) ) // gives e.g. TRUE GotoBufferId( bufferI )
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
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
<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.
- Programming Tasks
- Prime Numbers
- 11l
- AArch64 Assembly
- Ada
- ALGOL 68
- ALGOL 68-primes
- ALGOL W
- APL
- AppleScript
- ARM Assembly
- Arturo
- AWK
- BASIC
- BCPL
- C
- C++
- CLU
- COBOL
- Common Lisp
- Crystal
- Delphi
- Erlang
- F Sharp
- Factor
- Fermat
- Forth
- FreeBASIC
- Go
- J
- Java
- Jq
- Haskell
- Julia
- Kotlin
- Ksh
- Lua
- Mathematica
- Wolfram Language
- Modula-2
- Nim
- Pari/GP
- Pascal
- Perl
- Ntheory
- Phix
- PicoLisp
- PILOT
- PL/I
- PL/M
- Polyglot:PL/I and PL/M
- Processing
- PureBasic
- Python
- Quackery
- Racket
- Raku
- Red
- REXX
- Ring
- Ruby
- Rust
- Sage
- Seed7
- Sidef
- TSE SAL
- Swift
- Wren
- Wren-math
- Wren-fmt
- XPL0