Additive primes: Difference between revisions
Added C# example |
|||
(121 intermediate revisions by 56 users not shown) | |||
Line 17: | Line 17: | ||
:* the prime-numbers fandom: [https://prime-numbers.fandom.com/wiki/Additive_Primes additive primes]. |
:* the prime-numbers fandom: [https://prime-numbers.fandom.com/wiki/Additive_Primes additive primes]. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight 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’)</syntaxhighlight> |
|||
{{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> |
|||
=={{header|AArch64 Assembly}}== |
|||
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }} |
|||
<syntaxhighlight 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" |
|||
</syntaxhighlight> |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|ABC}}== |
|||
<syntaxhighlight lang="abc">HOW TO REPORT prime n: |
|||
REPORT n>=2 AND NO d IN {2..floor root n} HAS n mod d = 0 |
|||
HOW TO RETURN digit.sum n: |
|||
SELECT: |
|||
n<10: RETURN n |
|||
ELSE: RETURN (n mod 10) + digit.sum floor (n/10) |
|||
HOW TO REPORT additive.prime n: |
|||
REPORT prime n AND prime digit.sum n |
|||
PUT 0 IN n |
|||
FOR i IN {1..499}: |
|||
IF additive.prime i: |
|||
WRITE i>>4 |
|||
PUT n+1 IN n |
|||
IF n mod 10 = 0: WRITE / |
|||
WRITE / |
|||
WRITE "There are `n` additive primes less than 500."/</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes less than 500.</pre> |
|||
=={{header|Action!}}== |
|||
{{libheader|Action! Sieve of Eratosthenes}} |
|||
<syntaxhighlight lang="action!"> |
|||
;;; find some additive primes - primes whose digit sum is also prime |
|||
;;; Library: Action! Sieve of Eratosthenes |
|||
INCLUDE "H6:SIEVE.ACT" |
|||
PROC Main() |
|||
DEFINE MAX_PRIME = "500" |
|||
BYTE ARRAY primes(MAX_PRIME) |
|||
CARD n, digitSum, v, count |
|||
Sieve(primes,MAX_PRIME) |
|||
count = 0 |
|||
FOR n = 1 TO MAX_PRIME - 1 DO |
|||
IF primes( n ) THEN |
|||
digitSum = 0 |
|||
v = n |
|||
WHILE v > 0 DO |
|||
digitSum ==+ v MOD 10 |
|||
v ==/ 10 |
|||
OD |
|||
IF primes( digitSum ) THEN |
|||
IF n < 100 THEN |
|||
Put(' ) |
|||
IF n < 10 THEN Put(' ) FI |
|||
FI |
|||
Put(' )PrintI( n ) |
|||
count ==+ 1 |
|||
IF count MOD 20 = 0 THEN PutE() FI |
|||
FI |
|||
FI |
|||
OD |
|||
PutE()Print( "Found " )PrintI( count )Print( " additive primes below " )PrintI( MAX_PRIME + 1 )PutE() |
|||
RETURN |
|||
</syntaxhighlight> |
|||
{{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 below 501 |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight 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;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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.</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find additive primes - primes whose digit sum is also prime # |
||
# sieve the primes to max prime # |
# sieve the primes to max prime # |
||
PR read "primes.incl.a68" PR |
PR read "primes.incl.a68" PR |
||
Line 42: | Line 428: | ||
FI |
FI |
||
OD; |
OD; |
||
print( ( newline, "Found ", whole( additive count, 0 ) |
print( ( newline, "Found ", whole( additive count, 0 ) ) ); |
||
print( ( " additive primes below ", whole( UPB prime + 1, 0 ), newline ) ) |
|||
END</lang> |
|||
END</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 53: | Line 440: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight 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 % |
% sets p( 1 :: n ) to a sieve of primes up to n % |
||
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ; |
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ; |
||
Line 92: | Line 479: | ||
write( i_w := 1, s_w := 0, "Found ", aCount, " additive primes below ", MAX_NUMBER ) |
write( i_w := 1, s_w := 0, "Found ", aCount, " additive primes below ", MAX_NUMBER ) |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 103: | Line 490: | ||
=={{header|APL}}== |
=={{header|APL}}== |
||
< |
<syntaxhighlight lang="apl">((+⌿(4/10)⊤P)∊P)/P←(~P∊P∘.×P)/P←1↓⍳500</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 111: | Line 498: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
< |
<syntaxhighlight lang="applescript">on sieveOfEratosthenes(limit) |
||
script o |
script o |
||
property numberList : {missing value} |
property numberList : {missing value} |
||
Line 156: | Line 543: | ||
-- Task code: |
-- Task code: |
||
tell additivePrimes(499) to return {|additivePrimes<500|:it, numberThereof:count}</ |
tell additivePrimes(499) to return {|additivePrimes<500|:it, numberThereof:count}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<syntaxhighlight 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}</syntaxhighlight> |
||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
|||
<syntaxhighlight 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" |
|||
</syntaxhighlight> |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">additives: select 2..500 'x -> and? prime? x prime? sum digits x |
||
loop split.every:10 additives 'a -> |
loop split.every:10 additives 'a -> |
||
print map a => [pad to :string & 4] |
print map a => [pad to :string & 4] |
||
print ["\nFound" size additives "additive primes up to 500"]</ |
print ["\nFound" size additives "additive primes up to 500"]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 182: | Line 774: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f ADDITIVE_PRIMES.AWK |
# syntax: GAWK -f ADDITIVE_PRIMES.AWK |
||
BEGIN { |
BEGIN { |
||
Line 212: | Line 804: | ||
return(sum) |
return(sum) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 225: | Line 817: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
< |
<syntaxhighlight lang="basic">10 DEFINT A-Z: E=500 |
||
20 DIM P(E): P(0)=-1: P(1)=-1 |
20 DIM P(E): P(0)=-1: P(1)=-1 |
||
30 FOR I=2 TO SQR(E) |
30 FOR I=2 TO SQR(E) |
||
Line 235: | Line 827: | ||
90 IF NOT P(S) THEN N=N+1: PRINT I, |
90 IF NOT P(S) THEN N=N+1: PRINT I, |
||
100 NEXT |
100 NEXT |
||
110 PRINT: PRINT N;" additive primes found below ";E</ |
110 PRINT: PRINT N;" additive primes found below ";E</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 2 3 5 7 11 |
<pre> 2 3 5 7 11 |
||
Line 249: | Line 841: | ||
461 463 467 487 |
461 463 467 487 |
||
54 additive primes found below 500</pre> |
54 additive primes found below 500</pre> |
||
==={{header|Applesoft BASIC}}=== |
|||
<syntaxhighlight lang="gwbasic"> 0 E = 500 |
|||
1 F = E - 1:L = LEN ( STR$ (F)) + 1: FOR I = 2 TO L:S$ = S$ + CHR$ (32): NEXT I: DIM P(E):P(0) = - 1:P(1) = - 1: FOR I = 2 TO SQR (F): IF NOT P(I) THEN FOR J = I * 2 TO E STEP I:P(J) = - 1: NEXT J |
|||
2 NEXT I: FOR I = B TO F: IF NOT P(I) THEN GOSUB 4 |
|||
3 NEXT I: PRINT : PRINT N" ADDITIVE PRIMES FOUND BELOW "E;: END |
|||
4 S = 0: IF I THEN FOR J = I TO 0 STEP 0:J1 = INT (J / 10):S = S + (J - J1 * 10):J = J1: NEXT J |
|||
5 IF NOT P(S) THEN N = N + 1: PRINT RIGHT$ (S$ + STR$ (I),L); |
|||
6 RETURN</syntaxhighlight> |
|||
<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 |
|||
54 ADDITIVE PRIMES FOUND BELOW 500 |
|||
</pre> |
|||
==={{header|BASIC256}}=== |
|||
<syntaxhighlight lang="freebasic">print "Prime", "Digit Sum" |
|||
for i = 2 to 499 |
|||
if isprime(i) then |
|||
s = digSum(i) |
|||
if isPrime(s) then print i, s |
|||
end if |
|||
next i |
|||
end |
|||
function isPrime(v) |
|||
if v < 2 then return False |
|||
if v mod 2 = 0 then return v = 2 |
|||
if v mod 3 = 0 then return v = 3 |
|||
d = 5 |
|||
while d * d <= v |
|||
if v mod d = 0 then return False else d += 2 |
|||
end while |
|||
return True |
|||
end function |
|||
function digsum(n) |
|||
s = 0 |
|||
while n |
|||
s += n mod 10 |
|||
n /= 10 |
|||
end while |
|||
return s |
|||
end function</syntaxhighlight> |
|||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang="bcpl">get "libhdr" |
||
manifest $( limit = 500 $) |
manifest $( limit = 500 $) |
||
Line 285: | Line 919: | ||
$) |
$) |
||
writef("*N*NFound %N additive primes < %N.*N", num, limit) |
writef("*N*NFound %N additive primes < %N.*N", num, limit) |
||
$)</ |
$)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 2 3 5 7 11 23 29 41 43 47 |
<pre> 2 3 5 7 11 23 29 41 43 47 |
||
Line 295: | Line 929: | ||
Found 54 additive primes < 500.</pre> |
Found 54 additive primes < 500.</pre> |
||
=={{header|C}}== |
|||
<syntaxhighlight 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 */ |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
Line 338: | Line 1,060: | ||
} |
} |
||
std::cout << '\n' << count << " additive primes found.\n"; |
std::cout << '\n' << count << " additive primes found.\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 350: | Line 1,072: | ||
461 463 467 487 |
461 463 467 487 |
||
54 additive primes found. |
54 additive primes found. |
||
</pre> |
|||
=={{header|C sharp|C#}}== |
|||
<syntaxhighlight lang="csharp"> |
|||
internal class Program |
|||
{ |
|||
private static void Main(string[] args) |
|||
{ |
|||
long primeCandidate = 1; |
|||
long additivePrimeCount = 0; |
|||
Console.WriteLine("Additive Primes"); |
|||
while (primeCandidate < 500) |
|||
{ |
|||
if (IsAdditivePrime(primeCandidate)) |
|||
{ |
|||
additivePrimeCount++; |
|||
Console.Write($"{primeCandidate,-3} "); |
|||
if (additivePrimeCount % 10 == 0) |
|||
{ |
|||
Console.WriteLine(); |
|||
} |
|||
} |
|||
primeCandidate++; |
|||
} |
|||
Console.WriteLine(); |
|||
Console.WriteLine($"Found {additivePrimeCount} additive primes less than 500"); |
|||
} |
|||
private static bool IsAdditivePrime(long number) |
|||
{ |
|||
if (IsPrime(number) && IsPrime(DigitSum(number))) |
|||
{ |
|||
return true; |
|||
} |
|||
return false; |
|||
} |
|||
private static bool IsPrime(long number) |
|||
{ |
|||
if (number < 2) |
|||
{ |
|||
return false; |
|||
} |
|||
if (number % 2 == 0) |
|||
{ |
|||
return number == 2; |
|||
} |
|||
if (number % 3 == 0) |
|||
{ |
|||
return number == 3; |
|||
} |
|||
int delta = 2; |
|||
long k = 5; |
|||
while (k * k <= number) |
|||
{ |
|||
if (number % k == 0) |
|||
{ |
|||
return false; |
|||
} |
|||
k += delta; |
|||
delta = 6 - delta; |
|||
} |
|||
return true; |
|||
} |
|||
private static long DigitSum(long n) |
|||
{ |
|||
long sum = 0; |
|||
while (n > 0) |
|||
{ |
|||
sum += n % 10; |
|||
n /= 10; |
|||
} |
|||
return sum; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Additive Primes |
|||
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> |
|||
=={{header|CLU}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{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 < 500</pre> |
|||
=={{header|COBOL}}== |
|||
<syntaxhighlight 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).</syntaxhighlight> |
|||
{{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 |
|||
Amount of additive primes found: 54</pre> |
|||
=={{header|Common Lisp}}== |
|||
<syntaxhighlight 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)))) ) |
|||
</syntaxhighlight> |
|||
{{out}}<pre>(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 |
|||
</pre> |
|||
=={{header|Crystal}}== |
|||
<syntaxhighlight 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}." |
|||
</syntaxhighlight> |
|||
{{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 |
|||
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. |
|||
</pre> |
|||
=={{header|Dart}}== |
|||
<syntaxhighlight lang="dart">import 'dart:math'; |
|||
void main() { |
|||
const limit = 500; |
|||
print('Additive primes less than $limit :'); |
|||
int count = 0; |
|||
for (int n = 1; n < limit; ++n) { |
|||
if (isPrime(digit_sum(n)) && isPrime(n)) { |
|||
print(' $n'); |
|||
++count; |
|||
} |
|||
} |
|||
print('$count additive primes found.'); |
|||
} |
|||
bool isPrime(int n) { |
|||
if (n <= 1) return false; |
|||
if (n == 2) return true; |
|||
for (int i = 2; i <= sqrt(n); ++i) { |
|||
if (n % i == 0) return false; |
|||
} |
|||
return true; |
|||
} |
|||
int digit_sum(int n) { |
|||
int sum = 0; |
|||
for (int m = n; m > 0; m ~/= 10) sum += m % 10; |
|||
return sum; |
|||
}</syntaxhighlight> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
Many Rosette Code problems have similar operations. This problem was solved using subroutines that were written and used for other problems. Instead of packing all the operations in a single block of code, this example shows the advantage of breaking operations into separate modules that aids in code resuse. |
|||
<syntaxhighlight lang="Delphi"> |
|||
{These routines would normally be in libraries but are shown here for clarity} |
|||
function IsPrime(N: int64): boolean; |
|||
{Fast, optimised prime test} |
|||
var I,Stop: int64; |
|||
begin |
|||
if (N = 2) or (N=3) then Result:=true |
|||
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false |
|||
else |
|||
begin |
|||
I:=5; |
|||
Stop:=Trunc(sqrt(N+0.0)); |
|||
Result:=False; |
|||
while I<=Stop do |
|||
begin |
|||
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; |
|||
Inc(I,6); |
|||
end; |
|||
Result:=True; |
|||
end; |
|||
end; |
|||
function SumDigits(N: integer): integer; |
|||
{Sum the integers in a number} |
|||
var T: integer; |
|||
begin |
|||
Result:=0; |
|||
repeat |
|||
begin |
|||
T:=N mod 10; |
|||
N:=N div 10; |
|||
Result:=Result+T; |
|||
end |
|||
until N<1; |
|||
end; |
|||
procedure ShowDigitSumPrime(Memo: TMemo); |
|||
var N,Sum,Cnt: integer; |
|||
var NS,S: string; |
|||
begin |
|||
Cnt:=0; |
|||
S:=''; |
|||
for N:=1 to 500-1 do |
|||
if IsPrime(N) then |
|||
begin |
|||
Sum:=SumDigits(N); |
|||
if IsPrime(Sum) then |
|||
begin |
|||
Inc(Cnt); |
|||
S:=S+Format('%6d',[N]); |
|||
if (Cnt mod 8)=0 then S:=S+CRLF; |
|||
end; |
|||
end; |
|||
Memo.Lines.Add(S); |
|||
Memo.Lines.Add('Count = '+IntToStr(Cnt)); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{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 |
|||
Count = 54 |
|||
Elapsed Time: 2.812 ms. |
|||
</pre> |
|||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/Additive_primes#Pascal Pascal]. |
|||
=={{header|Draco}}== |
|||
<syntaxhighlight lang="draco">proc sieve([*] bool prime) void: |
|||
word max, p, c; |
|||
max := dim(prime,1)-1; |
|||
prime[0] := false; |
|||
prime[1] := false; |
|||
for p from 2 upto max do prime[p] := true od; |
|||
for p from 2 upto max/2 do |
|||
for c from p*2 by p upto max do |
|||
prime[c] := false |
|||
od |
|||
od |
|||
corp |
|||
proc digit_sum(word num) byte: |
|||
byte sum; |
|||
sum := 0; |
|||
while |
|||
sum := sum + num % 10; |
|||
num := num / 10; |
|||
num /= 0 |
|||
do od; |
|||
sum |
|||
corp |
|||
proc main() void: |
|||
word MAX = 500; |
|||
word p, n; |
|||
[MAX]bool prime; |
|||
sieve(prime); |
|||
n := 0; |
|||
for p from 2 upto MAX-1 do |
|||
if prime[p] and prime[digit_sum(p)] then |
|||
write(p:4); |
|||
n := n + 1; |
|||
if n % 20 = 0 then writeln() fi |
|||
fi |
|||
od; |
|||
writeln(); |
|||
writeln("There are ", n, " additive primes below ", MAX) |
|||
corp</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes below 500</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang="easylang"> |
|||
func prime n . |
|||
if n mod 2 = 0 and n > 2 |
|||
return 0 |
|||
. |
|||
i = 3 |
|||
sq = sqrt n |
|||
while i <= sq |
|||
if n mod i = 0 |
|||
return 0 |
|||
. |
|||
i += 2 |
|||
. |
|||
return 1 |
|||
. |
|||
func digsum n . |
|||
while n > 0 |
|||
sum += n mod 10 |
|||
n = n div 10 |
|||
. |
|||
return sum |
|||
. |
|||
for i = 2 to 500 |
|||
if prime i = 1 |
|||
s = digsum i |
|||
if prime s = 1 |
|||
write i & " " |
|||
. |
|||
. |
|||
. |
|||
print "" |
|||
</syntaxhighlight> |
|||
=={{header|Erlang}}== |
|||
<syntaxhighlight 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). |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
</pre> |
||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Additive Primes. Nigel Galloway: March 22nd., 2021 |
// 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) |
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 "" |
primes32()|>Seq.takeWhile((>)500)|>Seq.filter(fN 0>>isPrime)|>Seq.iter(printf "%d "); printfn "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<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 |
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 |
||
</pre> |
</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-02-05}} |
{{works with|Factor|0.99 2021-02-05}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting grouping io kernel math math.primes |
||
prettyprint sequences ; |
prettyprint sequences ; |
||
Line 373: | Line 1,680: | ||
499 primes-upto [ sum-digits prime? ] filter |
499 primes-upto [ sum-digits prime? ] filter |
||
[ 9 group simple-table. nl ] |
[ 9 group simple-table. nl ] |
||
[ length "Found %d additive primes < 500.\n" printf ] bi</ |
[ length "Found %d additive primes < 500.\n" printf ] bi</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 385: | Line 1,692: | ||
Found 54 additive primes < 500. |
Found 54 additive primes < 500. |
||
</pre> |
</pre> |
||
=={{header|Fermat}}== |
|||
<syntaxhighlight 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);</syntaxhighlight> |
|||
{{out}}<pre> |
|||
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</pre> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|Gforth}} |
{{works with|Gforth}} |
||
< |
<syntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ; |
||
: notprime! ( n -- ) here + 1 swap c! ; |
: notprime! ( n -- ) here + 1 swap c! ; |
||
Line 427: | Line 1,811: | ||
500 print_additive_primes |
500 print_additive_primes |
||
bye</ |
bye</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 443: | Line 1,827: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
As with the other special primes tasks, use one of the primality testing algorithms as an include. |
As with the other special primes tasks, use one of the primality testing algorithms as an include. |
||
< |
<syntaxhighlight lang="freebasic">#include "isprime.bas" |
||
function digsum( n as uinteger ) as uinteger |
function digsum( n as uinteger ) as uinteger |
||
Line 464: | Line 1,848: | ||
end if |
end if |
||
end if |
end if |
||
next i</ |
next i</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:16em">Prime Digit Sum |
<pre style="height:16em">Prime Digit Sum |
||
Line 521: | Line 1,905: | ||
467 17 |
467 17 |
||
487 19</pre> |
487 19</pre> |
||
=={{header|Free Pascal}}== |
|||
Using Sieve of Eratosthenes to find all primes upto 500, |
|||
then go through the list, sum digits and check for prime |
|||
<syntaxhighlight lang="pascal"> |
|||
Program AdditivePrimes; |
|||
Const max_number = 500; |
|||
Var is_prime : array Of Boolean; |
|||
Procedure sieve(Var arr: Array Of boolean ); |
|||
{use Sieve of Eratosthenes to find all primes to max number} |
|||
Var i,j : NativeUInt; |
|||
Begin |
|||
For i := 2 To high(arr) Do |
|||
arr[i] := True; // set all bits to be True |
|||
For i := 2 To high(arr) Do |
|||
Begin |
|||
If (arr[i]) Then |
|||
For j := 2 To (high(arr) Div i) Do |
|||
arr[i * j] := False; |
|||
End; |
|||
End; |
|||
Function GetSumOfDigits(num: NativeUInt): longint; |
|||
{calcualte the sum of digits of a number} |
|||
Var |
|||
sum : longint = 0; |
|||
dummy: NativeUInt; |
|||
Begin |
|||
Repeat |
|||
dummy := num; |
|||
num := num Div 10; |
|||
Inc(sum, dummy - (num SHL 3 + num SHL 1)); |
|||
Until num < 1; |
|||
GetSumOfDigits := sum; |
|||
End; |
|||
Var x : NativeUInt = 2; {first prime} |
|||
counter : longint = 0; |
|||
Begin |
|||
setlength(is_prime,max_number); //set length of array to max_number |
|||
Sieve(is_prime); //apply Sieve |
|||
{since 2 is the only even prime, let's do it separate} |
|||
If is_prime[x] And is_prime[GetSumOfDigits(x)] Then |
|||
Begin |
|||
write(x:4); |
|||
inc(counter); |
|||
End; |
|||
inc(x); |
|||
While x < max_number Do |
|||
Begin |
|||
If is_prime[x] And is_prime[GetSumOfDigits(x)] Then |
|||
Begin |
|||
if counter mod 10 = 0 then writeln(); |
|||
write(x:4); |
|||
inc(counter); |
|||
End; |
|||
inc(x,2); |
|||
End; |
|||
writeln(); |
|||
writeln(); |
|||
writeln(counter,' additive primes found.'); |
|||
End. |
|||
</syntaxhighlight> |
|||
{{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 |
|||
54 additive primes found. |
|||
</pre> |
|||
=={{header|Frink}}== |
|||
<syntaxhighlight lang="frink">vals = toArray[select[primes[2, 500], {|x| isPrime[sum[integerDigits[x]]]}]] |
|||
println[formatTable[columnize[vals, 10]]] |
|||
println["\n" + length[vals] + " values found."]</syntaxhighlight> |
|||
{{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 |
|||
54 values found. |
|||
</pre> |
|||
=={{header|FutureBasic}}== |
|||
<syntaxhighlight lang="futurebasic"> |
|||
local fn IsPrime( n as NSUInteger ) as BOOL |
|||
NSUInteger i |
|||
BOOL result = YES |
|||
if ( n < 2 ) then exit fn = NO |
|||
for i = 2 to n + 1 |
|||
if ( i * i <= n ) and ( n mod i == 0 ) |
|||
exit fn = NO |
|||
end if |
|||
next |
|||
end fn = result |
|||
local fn DigSum( n as NSUInteger ) as NSUInteger |
|||
NSUInteger s = 0 |
|||
while ( n > 0 ) |
|||
s += ( n mod 10 ) |
|||
n /= 10 |
|||
wend |
|||
end fn = s |
|||
void local fn AdditivePrimes( n as NSUInteger ) |
|||
NSUInteger i, s = 0, counter = 0 |
|||
printf @"Additive Primes:" |
|||
for i = 2 to n |
|||
if ( fn IsPrime(i) ) and ( fn IsPrime( fn DigSum(i) ) ) |
|||
s++ |
|||
printf @"%4ld \b", i : counter++ |
|||
if counter == 10 then counter = 0 : print |
|||
end if |
|||
next |
|||
printf @"\n\nFound %lu additive primes less than %lu.", s, n |
|||
end fn |
|||
fn AdditivePrimes( 500 ) |
|||
HandleEvents |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
Additive Primes: |
|||
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> |
|||
=={{header|Fōrmulæ}}== |
|||
{{FormulaeEntry|page=https://formulae.org/?script=examples/Additive_primes}} |
|||
'''Solution''' |
|||
[[File:Fōrmulæ - Additive primes 01.png]] |
|||
'''Test case 1.''' Write a program to determine all additive primes less than 500. |
|||
[[File:Fōrmulæ - Additive primes 02.png]] |
|||
[[File:Fōrmulæ - Additive primes 03.png]] |
|||
'''Test case 2.''' Show the number of additive primes. |
|||
[[File:Fōrmulæ - Additive primes 04.png]] |
|||
[[File:Fōrmulæ - Additive primes 05.png]] |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 582: | Line 2,135: | ||
} |
} |
||
fmt.Printf("\n\n%d additive primes found.\n", count) |
fmt.Printf("\n\n%d additive primes found.\n", count) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 596: | Line 2,149: | ||
54 additive primes found. |
54 additive primes found. |
||
</pre> |
</pre> |
||
=={{header|J}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight 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; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{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> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 602: | Line 2,202: | ||
'''Preliminaries''' |
'''Preliminaries''' |
||
< |
<syntaxhighlight lang="jq">def is_prime: |
||
. as $n |
. as $n |
||
| if ($n < 2) then false |
| if ($n < 2) then false |
||
Line 634: | Line 2,234: | ||
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''The task''' |
'''The task''' |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# Input: a number n |
# Input: a number n |
||
# Output: an array of additive primes less than n |
# Output: an array of additive primes less than n |
||
Line 653: | Line 2,253: | ||
| ((nwise(10) | map(lpad(4)) | join(" ")), |
| ((nwise(10) | map(lpad(4)) | join(" ")), |
||
"\n\(length) additive primes found.")) |
"\n\(length) additive primes found.")) |
||
</ |
</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 666: | Line 2,266: | ||
54 additive primes found. |
54 additive primes found. |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
Naive solution which doesn't rely on advanced number theoretic libraries. |
|||
<syntaxhighlight 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 |
|||
</syntaxhighlight> |
|||
The task |
|||
<pre>λ> 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]</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
let |
let |
||
Line 682: | Line 2,319: | ||
println("\n\n$pcount additive primes found.") |
println("\n\n$pcount additive primes found.") |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Erdős primes under 500: |
Erdős primes under 500: |
||
Line 688: | Line 2,325: | ||
157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 |
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 |
353 359 373 379 397 401 409 421 443 449 461 463 467 487 |
||
54 additive primes found. |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight 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") |
|||
}</syntaxhighlight> |
|||
{{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> |
|||
=={{header|Ksh}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{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 </pre> |
|||
=={{header|Lambdatalk}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
{def isprime |
|||
{def isprime.loop |
|||
{lambda {:n :m :i} |
|||
{if {> :i :m} |
|||
then true |
|||
else {if {= {% :n :i} 0} |
|||
then false |
|||
else {isprime.loop :n :m {+ :i 2}} |
|||
}}}} |
|||
{lambda {:n} |
|||
{if {or {= :n 2} {= :n 3} {= :n 5} {= :n 7}} |
|||
then true |
|||
else {if {or {< : n 2} {= {% :n 2} 0}} |
|||
then false |
|||
else {isprime.loop :n {sqrt :n} 3} |
|||
}}}} |
|||
-> isprime |
|||
{def digit.sum |
|||
{def digit.sum.loop |
|||
{lambda {:n :sum} |
|||
{if {> :n 0} |
|||
then {digit.sum.loop {floor {/ :n 10}} |
|||
{+ :sum {% :n 10}}} |
|||
else :sum}}} |
|||
{lambda {:n} |
|||
{digit.sum.loop :n 0}}} |
|||
-> digit.sum |
|||
{S.replace \s by space in |
|||
{S.map {lambda {:i} |
|||
{if {and {isprime :i} |
|||
{isprime {digit.sum :i}}} |
|||
then :i |
|||
else}} |
|||
{S.serie 2 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 |
|||
i.e 54 additive primes until 500. |
|||
</syntaxhighlight> |
|||
=={{header|langur}}== |
|||
<syntaxhighlight lang="langur">val isPrime = fn(i) { |
|||
i == 2 or i > 2 and |
|||
not any(fn x: i div x, pseries(2 .. i ^/ 2)) |
|||
} |
|||
val sumDigits = fn i: fold(fn{+}, s2n(string(i))) |
|||
writeln "Additive primes less than 500:" |
|||
var cnt = 0 |
|||
for i in [2] ~ series(3..500, 2) { |
|||
if isPrime(i) and isPrime(sumDigits(i)) { |
|||
write "{{i:3}} " |
|||
cnt += 1 |
|||
if cnt div 10: writeln() |
|||
} |
|||
} |
|||
writeln "\n\n{{cnt}} additive primes found.\n" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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. |
54 additive primes found. |
||
Line 694: | Line 2,498: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
This task uses <code>primegen</code> from: [[Extensible_prime_generator#Lua]] |
This task uses <code>primegen</code> from: [[Extensible_prime_generator#Lua]] |
||
< |
<syntaxhighlight lang="lua">function sumdigits(n) |
||
local sum = 0 |
local sum = 0 |
||
while n > 0 do |
while n > 0 do |
||
Line 706: | Line 2,510: | ||
aprimes = primegen:filter(function(n) return primegen.tbd(sumdigits(n)) end) |
aprimes = primegen:filter(function(n) return primegen.tbd(sumdigits(n)) end) |
||
print(table.concat(aprimes, " ")) |
print(table.concat(aprimes, " ")) |
||
print("Count:", #aprimes)</ |
print("Count:", #aprimes)</syntaxhighlight> |
||
{{out}} |
{{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 |
<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 |
||
Line 712: | Line 2,516: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[AdditivePrimeQ] |
||
AdditivePrimeQ[n_Integer] := PrimeQ[n] \[And] PrimeQ[Total[IntegerDigits[n]]] |
AdditivePrimeQ[n_Integer] := PrimeQ[n] \[And] PrimeQ[Total[IntegerDigits[n]]] |
||
Select[Range[500], AdditivePrimeQ]</ |
Select[Range[500], AdditivePrimeQ]</syntaxhighlight> |
||
{{out}} |
{{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}</pre> |
<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}</pre> |
||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima"> |
|||
/* Function that returns a list of digits given a nonnegative integer */ |
|||
decompose(num) := block([digits, remainder], |
|||
digits: [], |
|||
while num > 0 do |
|||
(remainder: mod(num, 10), |
|||
digits: cons(remainder, digits), |
|||
num: floor(num/10)), |
|||
digits |
|||
)$ |
|||
/* Routine that extracts from primes between 2 and 500, inclusive, the additive primes */ |
|||
block( |
|||
primes(2,500), |
|||
sublist(%%,lambda([x],primep(apply("+",decompose(x)))))); |
|||
/* Number of additive primes in the rank */ |
|||
length(%); |
|||
</syntaxhighlight> |
|||
{{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] |
|||
54 |
|||
</pre> |
|||
=={{header|MiniScript}}== |
|||
<syntaxhighlight lang="miniscript"> |
|||
isPrime = function(n) |
|||
if n <= 3 then return n > 1 |
|||
if n % 2 == 0 or n % 3 == 0 then return false |
|||
i = 5 |
|||
while i ^ 2 <= n |
|||
if n % i == 0 or n % (i + 2) == 0 then return false |
|||
i += 6 |
|||
end while |
|||
return true |
|||
end function |
|||
digitSum = function(n) |
|||
sum = 0 |
|||
while n > 0 |
|||
sum += n % 10 |
|||
n = floor(n / 10) |
|||
end while |
|||
return sum |
|||
end function |
|||
additive = [] |
|||
for i in range(2, 500) |
|||
if isPrime(i) and isPrime(digitSum(i)) then additive.push(i) |
|||
end for |
|||
print "There are " + additive.len + " additive primes under 500." |
|||
print additive |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
miniscript.exe additive-prime.ms |
|||
There are 54 additive 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] |
|||
</pre> |
|||
=={{header|Miranda}}== |
|||
<syntaxhighlight lang="miranda">main :: [sys_message] |
|||
main = [Stdout (table 5 10 nums), Stdout countmsg] |
|||
where nums = filter additive_prime [1..500] |
|||
countmsg = "Found " ++ show (#nums) ++ " additive primes < 500\n" |
|||
table :: num->num->[num]->[char] |
|||
table w c ls = lay [concat (map (rjustify w . show) l) | l <- split c ls] |
|||
split :: num->[*]->[[*]] |
|||
split n ls = [ls], if #ls < n |
|||
= take n ls:split n (drop n ls), otherwise |
|||
additive_prime :: num->bool |
|||
additive_prime n = prime (dsum n) & prime n |
|||
dsum :: num->num |
|||
dsum n = n, if n<10 |
|||
= n mod 10 + dsum (n div 10), otherwise |
|||
prime :: num->bool |
|||
prime n = n>=2 & #[d | d<-[2..entier (sqrt n)]; n mod d=0] = 0</syntaxhighlight> |
|||
{{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 < 500</pre> |
|||
=={{header|Modula-2}}== |
|||
<syntaxhighlight 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.</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes less than 500.</pre> |
|||
=={{header|Modula-3}}== |
|||
{{trans|Modula-2}} |
|||
<syntaxhighlight lang="modula3">MODULE AdditivePrimes EXPORTS Main; |
|||
IMPORT SIO,Fmt; |
|||
CONST |
|||
Max = 500; |
|||
VAR |
|||
Count:CARDINAL := 0; |
|||
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 J: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; |
|||
INC(J,I) |
|||
END |
|||
END |
|||
END; |
|||
END Sieve; |
|||
BEGIN |
|||
Sieve(); |
|||
FOR N := 2 TO Max DO |
|||
IF Prime[N] AND Prime[DigitSum(N)] THEN |
|||
SIO.PutText(Fmt.F("%4s",Fmt.Int(N))); |
|||
INC(Count); |
|||
IF Count MOD 10 = 0 THEN SIO.Nl() END |
|||
END |
|||
END; |
|||
SIO.PutText(Fmt.F("\nThere are %s additive primes less than %s.\n", |
|||
Fmt.Int(Count),Fmt.Int(Max))); |
|||
END AdditivePrimes. |
|||
</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes less than 500.</pre> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import math, strutils |
||
const N = 499 |
const N = 499 |
||
Line 749: | Line 2,770: | ||
echo() |
echo() |
||
echo "\nNumber of additive primes found: ", count</ |
echo "\nNumber of additive primes found: ", count</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 761: | Line 2,782: | ||
Number of additive primes found: 54</pre> |
Number of additive primes found: 54</pre> |
||
=={{header|Oberon-07}}== |
|||
{{Trans|Modula-3}} |
|||
<syntaxhighlight lang="modula2"> |
|||
MODULE AdditivePrimes; |
|||
IMPORT |
|||
Out; |
|||
CONST |
|||
Max = 500; |
|||
VAR |
|||
Count, n :INTEGER; |
|||
Prime :ARRAY Max + 1 OF BOOLEAN; |
|||
PROCEDURE DigitSum( n :INTEGER ):INTEGER; |
|||
VAR result :INTEGER; |
|||
BEGIN |
|||
result := 0; |
|||
IF n < 10 THEN result := n |
|||
ELSE result := ( n MOD 10 ) + DigitSum( n DIV 10 ) |
|||
END |
|||
RETURN result |
|||
END DigitSum; |
|||
PROCEDURE Sieve; |
|||
VAR i, j :INTEGER; |
|||
BEGIN |
|||
Prime[ 0 ] := FALSE; Prime[ 1 ] := FALSE; |
|||
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 |
|||
Sieve; |
|||
FOR n := 2 TO Max DO |
|||
IF Prime[ n ] & Prime[ DigitSum( n ) ] THEN |
|||
Out.Int( n, 4 ); |
|||
Count := Count + 1; |
|||
IF Count MOD 20 = 0 THEN Out.Ln END |
|||
END |
|||
END; |
|||
Out.Ln;Out.String( "There are " );Out.Int( Count, 1 ); |
|||
Out.String( " additive primes less than " );Out.Int( Max, 1 ); |
|||
Out.String( "." );Out.Ln |
|||
END AdditivePrimes. |
|||
</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes less than 500. |
|||
</pre> |
|||
=={{header|OCaml}}== |
|||
<syntaxhighlight lang="ocaml">let rec digit_sum n = |
|||
if n < 10 then n else n mod 10 + digit_sum (n / 10) |
|||
let is_prime n = |
|||
let rec test x = |
|||
let q = n / x in x > q || x * q <> n && n mod (x + 2) <> 0 && test (x + 6) |
|||
in if n < 5 then n lor 1 = 3 else n land 1 <> 0 && n mod 3 <> 0 && test 5 |
|||
let is_additive_prime n = |
|||
is_prime n && is_prime (digit_sum n) |
|||
let () = |
|||
Seq.ints 0 |> Seq.take_while ((>) 500) |> Seq.filter is_additive_prime |
|||
|> Seq.iter (Printf.printf " %u") |> print_newline</syntaxhighlight> |
|||
{{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</pre> |
|||
=={{header|Pari/GP}}== |
|||
This is a good task for demonstrating several different ways to approach a simple problem. |
|||
<syntaxhighlight 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]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>%1 = [54, 54, 54, 54]</pre> |
|||
=={{header|Pascal}}== |
|||
{{works with|Free Pascal}}{{works with|Delphi}} checking isPrime(sum of digits) before testimg isprime(num) improves speed.<br>Tried to speed up calculation of sum of digits. |
|||
<syntaxhighlight 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. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 %</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use ntheory 'is_prime'; |
use ntheory 'is_prime'; |
||
Line 778: | Line 3,056: | ||
is_prime($_) and is_prime(sum(split '',$_)) and push @ap, $_ for 1..$limit; |
is_prime($_) and is_prime(sum(split '',$_)) and push @ap, $_ for 1..$limit; |
||
print @ap . " additive primes < $limit:\n" . pp(@ap);</ |
print @ap . " additive primes < $limit:\n" . pp(@ap);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>54 additive primes < 500: |
<pre>54 additive primes < 500: |
||
Line 787: | Line 3,065: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">additive</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: # |
<span style="color: #008080;">function</span> <span style="color: #000000;">additive</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #004080;"> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">500</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">),</span><span style="color: #000000;">additive</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d additive primes found: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;"> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d additive primes found: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">))})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
54 additive primes found: 2 3 5 7 11 23 ... 443 449 461 463 467 487 |
54 additive primes found: 2 3 5 7 11 23 ... 443 449 461 463 467 487 |
||
</pre> |
</pre> |
||
=={{header|Phixmonti}}== |
|||
<syntaxhighlight lang="phixmonti">/# Rosetta Code problem: http://rosettacode.org/wiki/Additive_primes |
|||
by Galileo, 05/2022 #/ |
|||
include ..\Utilitys.pmt |
|||
def isprime |
|||
dup 1 <= if drop false |
|||
else dup 2 == not if |
|||
( dup sqrt 2 swap ) for |
|||
over swap mod not if drop false exitfor endif |
|||
endfor |
|||
endif |
|||
endif |
|||
false == not |
|||
enddef |
|||
def digitsum |
|||
0 swap dup 0 > while dup 10 mod rot + swap 10 / int dup 0 > endwhile |
|||
drop |
|||
enddef |
|||
0 500 for |
|||
dup isprime over digitsum isprime and if print " " print 1 + else drop endif |
|||
endfor |
|||
"Additive primes found: " print print |
|||
</syntaxhighlight> |
|||
{{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 Additive primes found: 54 |
|||
=== Press any key to exit ===</pre> |
|||
=={{header|Picat}}== |
|||
<syntaxhighlight lang="picat">main => |
|||
PCount = 0, |
|||
foreach (I in 2..499) |
|||
if prime(I) && prime(sum_digits(I)) then |
|||
PCount := PCount + 1, |
|||
printf("%4d ", I) |
|||
end |
|||
end, |
|||
printf("\n\n%d additive primes found.\n", PCount). |
|||
sum_digits(N) = S => |
|||
S = sum([ord(C)-ord('0') : C in to_string(N)]). |
|||
</syntaxhighlight> |
|||
{{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 |
|||
54 additive primes found. |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight 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) )</syntaxhighlight> |
|||
{{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 |
|||
Total count: 54 |
|||
</pre> |
|||
=={{header|PILOT}}== |
|||
<syntaxhighlight 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 :</syntaxhighlight> |
|||
{{out}} |
|||
<pre style='height:50ex;'>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</pre> |
|||
=={{header|PL/I}}== |
|||
See [[#Polyglot:PL/I and PL/M]] |
|||
=={{header|PL/M}}== |
=={{header|PL/M}}== |
||
See [[#Polyglot:PL/I and PL/M]] |
|||
<lang plm>100H: /* FIND ADDITIVE PRIMES - PRIMES WHOSE DIGIT SUM IS ALSO PRIME */ |
|||
=={{header|Polyglot:PL/I and PL/M}}== |
|||
DECLARE CR LITERALLY '0DH'; |
|||
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator) |
|||
DECLARE LF LITERALLY '0AH'; |
|||
Should work with many PL/I implementations. |
|||
<br> |
|||
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. |
|||
<syntaxhighlight 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 */ |
|||
BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */ |
|||
/* E.G. THE CP/M PL/I COMPILER DOESN'T LIKE THEM TO FOLLOW PROCEDURES */ |
|||
DECLARE FN BYTE, ARG ADDRESS; |
|||
/* PL/I */ |
|||
GOTO 5; |
|||
%replace dclsieve by 500; |
|||
END BDOS; |
|||
/* PL/M */ /* |
|||
PRINT$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END; |
|||
DECLARE DCLSIEVE LITERALLY '501'; |
|||
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; |
|||
/* PL/I DEFINITIONS */ |
|||
DECLARE MAX$PRIME LITERALLY '501'; |
|||
%include 'pg.inc'; |
|||
DECLARE FALSE LITERALLY '0'; |
|||
/* PL/M DEFINITIONS: CP/M BDOS SYSTEM CALL AND CONSOLE I/O ROUTINES, ETC. */ /* |
|||
DECLARE TRUE LITERALLY '1'; |
|||
DECLARE BINARY LITERALLY 'ADDRESS', CHARACTER LITERALLY 'BYTE'; |
|||
DECLARE FIXED LITERALLY ' ', BIT LITERALLY 'BYTE'; |
|||
DECLARE STATIC LITERALLY ' ', RETURNS LITERALLY ' '; |
|||
/* SIEVE THE PRIMES UP TO MAX$PRIME */ |
|||
DECLARE FALSE LITERALLY '0', TRUE LITERALLY '1'; |
|||
DECLARE HBOUND LITERALLY 'LAST', SADDR LITERALLY '.'; |
|||
BDOSF: PROCEDURE( FN, ARG )BYTE; |
|||
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END; |
|||
DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END; |
|||
DO I = 3 TO LAST( PRIME ) / 2 BY 2; |
|||
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END; |
|||
IF PRIME( I ) THEN DO; |
|||
PRCHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END; |
|||
PRSTRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END; |
|||
END; |
|||
PRNL: PROCEDURE; CALL PRCHAR( 0DH ); CALL PRCHAR( 0AH ); END; |
|||
END; |
|||
PRNUMBER: PROCEDURE( N ); |
|||
/* FIND THE PRIMES THAT ARE ADDATIVE PRIMES */ |
|||
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 ); |
|||
V |
DO WHILE( ( V := V / 10 ) > 0 ); |
||
N$STR( W := W - 1 ) = '0' + ( V MOD 10 ); |
|||
END; |
|||
CALL BDOS( 9, .N$STR( W ) ); |
|||
END PRNUMBER; |
|||
V = V / 10; |
|||
MODF: PROCEDURE( A, B )ADDRESS; |
|||
DECLARE ( A, B ) ADDRESS; |
|||
RETURN A MOD B; |
|||
END MODF; |
|||
A$COUNT = A$COUNT + 1; |
|||
/* END LANGUAGE DEFINITIONS */ |
|||
IF A$COUNT MOD 12 = 0 THEN CALL PRINT$NL; |
|||
END; |
|||
/* TASK */ |
|||
END; |
|||
/* PRIME ELEMENTS ARE 0, 1, ... 500 IN PL/M AND 1, 2, ... 500 IN PL/I */ |
|||
CALL PRINT$NL; |
|||
/* ELEMENT 0 IN PL/M IS IS UNUSED */ |
|||
CALL PRINT$NUMBER( A$COUNT, 4 ); |
|||
DECLARE PRIME( DCLSIEVE ) BIT; |
|||
CALL PRINT$STRING( .' ADDITIVE PRIMES FOUND BELOW$' ); |
|||
DECLARE ( MAXPRIME, MAXROOT, ACOUNT, I, J, DSUM, V ) FIXED BINARY; |
|||
CALL PRINT$NUMBER( LAST( PRIME ), 4 ); |
|||
/* SIEVE THE PRIMES UP TO MAX PRIME */ |
|||
CALL PRINT$NL; |
|||
PRIME( 1 ) = FALSE; PRIME( 2 ) = TRUE; |
|||
EOF |
|||
MAXPRIME = HBOUND( PRIME , 1 |
|||
</lang> |
|||
); |
|||
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;</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 872: | Line 3,366: | ||
313 317 331 337 353 359 373 379 397 401 409 421 |
313 317 331 337 353 359 373 379 397 401 409 421 |
||
443 449 461 463 467 487 |
443 449 461 463 467 487 |
||
FOUND 54 ADDITIVE PRIMES BELOW 500 |
|||
</pre> |
</pre> |
||
=={{header|Processing}}== |
=={{header|Processing}}== |
||
< |
<syntaxhighlight lang="processing">IntList primes = new IntList(); |
||
void setup() { |
void setup() { |
||
Line 912: | Line 3,405: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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 |
<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 |
||
Number of additive primes less than 500: 54</pre> |
Number of additive primes less than 500: 54</pre> |
||
=={{header|PureBasic}}== |
|||
<syntaxhighlight 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()</syntaxhighlight> |
|||
{{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 |
|||
54 additive primes below 500.</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight 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()</syntaxhighlight> |
|||
{{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> |
|||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
Line 923: | Line 3,476: | ||
<code>digitsum</code> is defined at [[Sum digits of an integer#Quackery]]. |
<code>digitsum</code> is defined at [[Sum digits of an integer#Quackery]]. |
||
< |
<syntaxhighlight lang="quackery"> 500 eratosthenes |
||
[] |
[] |
||
Line 932: | Line 3,485: | ||
[ i^ join ] ] ] |
[ i^ join ] ] ] |
||
dup echo cr cr |
dup echo cr cr |
||
size echo say " additive primes found."</ |
size echo say " additive primes found."</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 940: | Line 3,493: | ||
54 additive primes found.</pre> |
54 additive primes found.</pre> |
||
=={{header|R}}== |
|||
<syntaxhighlight lang="R"> |
|||
digitsum <- function(x) sum(floor(x / 10^(0:(nchar(x) - 1))) %% 10) |
|||
is.prime <- function(n) n == 2L || all(n %% 2L:max(2,floor(sqrt(n))) != 0) |
|||
range_int <- 2:500 |
|||
v <- sapply(range_int, \(x) is.prime(x) && is.prime(digitsum(x))) |
|||
cat(paste("Found",length(range_int[v]),"additive primes less than 500")) |
|||
print(range_int[v]) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Found 54 additive primes less than 500 |
|||
[1] 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 |
|||
[24] 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 |
|||
[47] 409 421 443 449 461 463 467 487</pre> |
|||
=={{header|Racket}}== |
|||
<syntaxhighlight 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)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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) |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>unit sub MAIN ($limit = 500); |
||
say "{+$_} additive primes < $limit:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}", |
say "{+$_} additive primes < $limit:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}", |
||
with ^$limit .grep: { .is-prime and .comb.sum.is-prime }</ |
with ^$limit .grep: { .is-prime and .comb.sum.is-prime }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>54 additive primes < 500: |
<pre>54 additive primes < 500: |
||
Line 953: | Line 3,546: | ||
353 359 373 379 397 401 409 421 443 449 |
353 359 373 379 397 401 409 421 443 449 |
||
461 463 467 487</pre> |
461 463 467 487</pre> |
||
=={{header|Red}}== |
|||
<syntaxhighlight 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 |
|||
</syntaxhighlight> |
|||
Uses <code>primes</code> defined in https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Red. |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program counts/displays the number of additive primes less than 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 |
call genP n /*generate all primes under N. */ |
||
w= |
w=5 /*width of a number in any column. */ |
||
title= 'additive primes that are < 'commas(n) |
|||
If cols>0 Then Say ' index ¦'center(title,cols*(w+1)+1) |
|||
If cols>0 Then Say '-------+'center('' ,cols*(w+1)+1,'-') |
|||
found=0 |
|||
found= 0; idx= 1 /*initialize # of additive primes & IDX*/ |
|||
ol='' /*a list of additive primes (so far). */ |
|||
idx=1 |
|||
do j=1 for #; p= @.j /*obtain the Jth prime. */ |
|||
Do j=1 By 1 |
|||
_= sumDigs(p); if \!._ then iterate /*is sum of J's digs a prime? No, skip.*/ /* ◄■■■■■■■■ a filter. */ |
|||
p=p.j /*obtain the Jth prime. */ |
|||
If p>n Then Leave /* no more needed */ |
|||
_=sumDigs(p) |
|||
c= commas(p) /*maybe add commas to the number. */ |
|||
If !._ Then Do |
|||
$= $ right(c, max(w, length(c) ) ) /*add additive prime──►list, allow big#*/ |
|||
found=found+1 /*bump the count of additive primes. */ |
|||
c=commas(p) /*maybe add commas To the number. */ |
|||
ol=ol right(c,max(w,length(c))) /*add additive prime--?list,allow big# */ |
|||
idx= idx + cols /*bump the index count for the output*/ |
|||
If words(ol)=10 Then Do /* a line is complete */ |
|||
end /*j*/ |
|||
Say center(idx,7)'¦' substr(ol,2) /*display what we have so far (cols). */ |
|||
ol='' /* prepare for next line */ |
|||
idx=idx+10 |
|||
End |
|||
End |
|||
End /*j*/ |
|||
If ol\=='' Then |
|||
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ |
|||
Say center(idx,7)'¦' substr(ol,2) /*possible display residual output. */ |
|||
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') |
|||
If cols>0 Then |
|||
say |
|||
Say '--------'center('',cols*(w+1)+1,'-') |
|||
say 'found ' commas(found) title |
|||
Say |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
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 |
|||
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 |
|||
genP: |
|||
#= 6; sq.#= @.# ** 2 /*the number of primes; prime squared.*/ |
|||
Parse Arg n |
|||
do j=@.#+2 by 2 for max(0, n%2-@.#%2-1) /*find odd primes from here on. */ |
|||
pl=2 3 5 7 11 13 |
|||
parse var j '' -1 _ /*obtain the last digit of the J var.*/ |
|||
!.=0 |
|||
if _==5 then iterate; if j// 3==0 then iterate /*J ÷ by 5? J ÷ by 3? */ |
|||
Do np=1 By 1 While pl<>'' |
|||
if j// 7==0 then iterate; if j//11==0 then iterate /*" " " 7? " " " 11? */ |
|||
Parse Var pl p pl |
|||
/* [↓] divide by the primes. ___ */ |
|||
p.np=p |
|||
do k=6 while sq.k<=j /*divide J by other primes ≤ √ J */ |
|||
sq.np=p*p |
|||
if j//@.k==0 then iterate j /*÷ by prev. prime? ¬prime ___ */ |
|||
!.p=1 |
|||
end /*k*/ /* [↑] only divide up to √ J */ |
|||
End |
|||
#= # + 1; @.#= j; sq.#= j*j; !.j= 1 /*bump prime count; assign prime & flag*/ |
|||
np=np-1 |
|||
end /*j*/; return</lang> |
|||
Do j=p.np+2 by 2 While j<n |
|||
Parse Var j '' -1 _ /*obtain the last digit of the J var.*/ |
|||
If _==5 Then Iterate |
|||
If j// 3==0 Then Iterate |
|||
If j// 7==0 Then Iterate |
|||
If j//11==0 Then Iterate |
|||
Do k=6 By 1 While sq.k<=j /*divide J by other primes <=sqrt(j) */ |
|||
If j//p.k==0 Then Iterate j /* not prime - try next */ |
|||
End /*k*/ |
|||
np=np+1 /*bump prime count; assign prime & flag*/ |
|||
p.np=j |
|||
sq.np=j*j |
|||
!.j=1 |
|||
End /*j*/ |
|||
Return</syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
index |
index ¦ additive primes that are < 500 |
||
-------+------------------------------------------------------------- |
|||
───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── |
|||
1 |
1 ¦ 2 3 5 7 11 23 29 41 43 47 |
||
11 |
11 ¦ 61 67 83 89 101 113 131 137 139 151 |
||
21 |
21 ¦ 157 173 179 191 193 197 199 223 227 229 |
||
31 |
31 ¦ 241 263 269 281 283 311 313 317 331 337 |
||
41 |
41 ¦ 353 359 373 379 397 401 409 421 443 449 |
||
51 |
51 ¦ 461 463 467 487 |
||
--------------------------------------------------------------------- |
|||
───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── |
|||
found 54 |
found 54 additive primes that are < 500 |
||
</pre> |
</pre> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
Line 1,043: | Line 3,675: | ||
see nl + "found " + row + " additive primes." + nl |
see nl + "found " + row + " additive primes." + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,056: | Line 3,688: | ||
found 54 additive primes. |
found 54 additive primes. |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|HP|49g}} |
|||
≪ →STR 0 |
|||
1 3 PICK SIZE '''FOR''' j |
|||
OVER j DUP SUB STR→ + '''NEXT''' NIP |
|||
≫ '<span style="color:blue>∑DIGITS</span>' STO |
|||
≪ { } 1 |
|||
'''DO''' |
|||
NEXTPRIME |
|||
'''IF''' DUP <span style="color:blue>∑DIGITS</span> ISPRIME? '''THEN''' SWAP OVER + SWAP '''END''' |
|||
'''UNTIL''' DUP 500 ≥ '''END''' |
|||
DROP DUP SIZE |
|||
≫ '<span style="color:blue>TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
2: { 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 } |
|||
1: 54 |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
|||
<syntaxhighlight 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}." |
|||
</syntaxhighlight> |
|||
{{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 |
|||
54 additive primes below 500. |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
===Flat implementation=== |
|||
<syntaxhighlight lang="rust">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}"); |
|||
}</syntaxhighlight> |
|||
{{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) |
|||
<syntaxhighlight lang="rust">// [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}"); |
|||
}</syntaxhighlight> |
|||
{{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> |
|||
=={{header|Sage}}== |
|||
<syntaxhighlight 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}") |
|||
</syntaxhighlight> |
|||
{{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> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func boolean: isPrime (in integer: number) is func |
const func boolean: isPrime (in integer: number) is func |
||
Line 1,104: | Line 3,851: | ||
end for; |
end for; |
||
writeln("\nFound " <& count <& " additive primes < 500."); |
writeln("\nFound " <& count <& " additive primes < 500."); |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,116: | Line 3,863: | ||
Found 54 additive primes < 500. |
Found 54 additive primes < 500. |
||
</pre> |
</pre> |
||
=={{header|SETL}}== |
|||
<syntaxhighlight lang="setl">program additive_primes; |
|||
loop for i in [i : i in [1..499] | additive_prime i] do |
|||
nprint(lpad(str i, 4)); |
|||
if (n +:= 1) mod 10 = 0 then |
|||
print; |
|||
end if; |
|||
end loop; |
|||
print; |
|||
print("There are " + str n + " additive primes less than 500."); |
|||
op additive_prime(n); |
|||
return prime n and prime digitsum n; |
|||
end op; |
|||
op prime(n); |
|||
return n>=2 and not exists d in {2..floor sqrt n} | n mod d = 0; |
|||
end op; |
|||
op digitsum(n); |
|||
loop while n>0; |
|||
s +:= n mod 10; |
|||
n div:= 10; |
|||
end loop; |
|||
return s; |
|||
end op; |
|||
end program; |
|||
</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes less than 500.</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func additive_primes(upto, base = 10) { |
||
upto.primes.grep { .sumdigits(base).is_prime } |
upto.primes.grep { .sumdigits(base).is_prime } |
||
} |
} |
||
Line 1,124: | Line 3,909: | ||
additive_primes(500).each_slice(10, {|*a| |
additive_primes(500).each_slice(10, {|*a| |
||
a.map { '%3s' % _ }.join(' ').say |
a.map { '%3s' % _ }.join(' ').say |
||
})</ |
})</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,134: | Line 3,919: | ||
461 463 467 487 |
461 463 467 487 |
||
</pre> |
</pre> |
||
=={{header|TSE SAL}}== |
|||
<syntaxhighlight 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 |
|||
</syntaxhighlight> |
|||
{{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 |
|||
</pre> |
|||
=={{header|Swift}}== |
|||
<syntaxhighlight 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.")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|uBasic/4tH}}== |
|||
{{trans|BASIC256}} |
|||
<syntaxhighlight lang="text">print "Prime", "Digit Sum" |
|||
for i = 2 to 499 |
|||
if func(_isPrime(i)) then |
|||
s = func(_digSum(i)) |
|||
if func(_isPrime(s)) then |
|||
print i, s |
|||
endif |
|||
endif |
|||
next |
|||
end |
|||
_isPrime |
|||
param (1) |
|||
local (1) |
|||
if a@ < 2 then return (0) |
|||
if a@ % 2 = 0 then return (a@ = 2) |
|||
if a@ % 3 = 0 then return (a@ = 3) |
|||
b@ = 5 |
|||
do while (b@ * b@) < (a@ + 1) |
|||
if a@ % b@ = 0 then unloop : return (0) |
|||
b@ = b@ + 2 |
|||
loop |
|||
return (1) |
|||
_digSum |
|||
param (1) |
|||
local (1) |
|||
b@ = 0 |
|||
do while a@ |
|||
b@ = b@ + (a@ % 10) |
|||
a@ = a@ / 10 |
|||
loop |
|||
return (b@)</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>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 |
|||
0 OK, 0:176</pre> |
|||
=={{header|Uiua}}== |
|||
{{works with|Uiua|0.10.0-dev.1}} |
|||
<syntaxhighlight lang="Uiua"> |
|||
[] # list of primes to be populated |
|||
↘2⇡500 # candidates (starting at 2) |
|||
# Take the first remaining candidate, which will be prime, save it, |
|||
# then remove every candidate that it divides. Repeat until none left. |
|||
⍢(▽≠0◿⊃⊢(.↘1)⟜(⊂⊢)|>0⧻) |
|||
# Tidy up. |
|||
⇌◌ |
|||
# Build sum of digits of each. |
|||
≡(/+≡⋕°⋕)... |
|||
# Mask out those that result in non-primes. |
|||
⊏⊚±⬚0⊏⊗ |
|||
# Return values and length. |
|||
⧻. |
|||
</syntaxhighlight> |
|||
{{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] |
|||
54 |
|||
</pre> |
|||
=={{header|V (Vlang)}}== |
|||
{{trans|go}} |
|||
<syntaxhighlight lang="v (vlang)">fn is_prime(n int) bool { |
|||
if n < 2 { |
|||
return false |
|||
} else if n%2 == 0 { |
|||
return n == 2 |
|||
} else if n%3 == 0 { |
|||
return n == 3 |
|||
} else { |
|||
mut d := 5 |
|||
for d*d <= n { |
|||
if n%d == 0 { |
|||
return false |
|||
} |
|||
d += 2 |
|||
if n%d == 0 { |
|||
return false |
|||
} |
|||
d += 4 |
|||
} |
|||
return true |
|||
} |
|||
} |
|||
fn sum_digits(nn int) int { |
|||
mut n := nn |
|||
mut sum := 0 |
|||
for n > 0 { |
|||
sum += n % 10 |
|||
n /= 10 |
|||
} |
|||
return sum |
|||
} |
|||
fn main() { |
|||
println("Additive primes less than 500:") |
|||
mut i := 2 |
|||
mut count := 0 |
|||
for { |
|||
if is_prime(i) && is_prime(sum_digits(i)) { |
|||
count++ |
|||
print("${i:3} ") |
|||
if count%10 == 0 { |
|||
println('') |
|||
} |
|||
} |
|||
if i > 2 { |
|||
i += 2 |
|||
} else { |
|||
i++ |
|||
} |
|||
if i > 499 { |
|||
break |
|||
} |
|||
} |
|||
println("\n\n$count additive primes found.") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|VTL-2}}== |
|||
<syntaxhighlight lang="vtl2">10 M=499 |
|||
20 :1)=1 |
|||
30 P=2 |
|||
40 :P)=0 |
|||
50 P=P+1 |
|||
60 #=M>P*40 |
|||
70 P=2 |
|||
80 C=P*2 |
|||
90 :C)=1 |
|||
110 C=C+P |
|||
120 #=M>C*90 |
|||
130 P=P+1 |
|||
140 #=M/2>P*80 |
|||
150 P=2 |
|||
160 N=0 |
|||
170 #=:P)*290 |
|||
180 S=0 |
|||
190 K=P |
|||
200 K=K/10 |
|||
210 S=S+% |
|||
220 #=0<K*200 |
|||
230 #=:S)*290 |
|||
240 ?=P |
|||
250 $=9 |
|||
260 N=N+1 |
|||
270 #=N/10*0+%=0=0*290 |
|||
280 ?="" |
|||
290 P=P+1 |
|||
300 #=M>P*170 |
|||
310 ?="" |
|||
320 ?="There are "; |
|||
330 ?=N |
|||
340 ?=" additive primes below "; |
|||
350 ?=M+1</syntaxhighlight> |
|||
{{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 |
|||
There are 54 additive primes below 500</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int |
||
import "/fmt" for Fmt |
import "./fmt" for Fmt |
||
var sumDigits = Fn.new { |n| |
var sumDigits = Fn.new { |n| |
||
Line 1,160: | Line 4,413: | ||
} |
} |
||
} |
} |
||
System.print("\n\n%(count) additive primes found.")</ |
System.print("\n\n%(count) additive primes found.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,176: | Line 4,429: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number |
||
int N, I; |
int N, I; |
||
[if N <= 1 then return false; |
[if N <= 1 then return false; |
||
Line 1,205: | Line 4,458: | ||
Text(0, " additive primes found below 500. |
Text(0, " additive primes found below 500. |
||
"); |
"); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,217: | Line 4,470: | ||
54 additive primes found below 500. |
54 additive primes found below 500. |
||
</pre> |
</pre> |
||
=={{header|Yabasic}}== |
|||
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Additive_primes |
|||
// by Galileo, 06/2022 |
|||
limit = 500 |
|||
dim flags(limit) |
|||
for i = 2 to limit |
|||
for k = i*i to limit step i |
|||
flags(k) = 1 |
|||
next |
|||
if flags(i) = 0 primes$ = primes$ + str$(i) + " " |
|||
next |
|||
dim prim$(1) |
|||
n = token(primes$, prim$()) |
|||
for i = 1 to n |
|||
sum = 0 |
|||
num$ = prim$(i) |
|||
for j = 1 to len(num$) |
|||
sum = sum + val(mid$(num$, j, 1)) |
|||
next |
|||
if instr(primes$, str$(sum) + " ") print prim$(i), " "; : count = count + 1 |
|||
next |
|||
print "\nFound: ", count</syntaxhighlight> |
|||
{{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 |
|||
---Program done, press RETURN---</pre> |
Revision as of 14:50, 30 June 2024
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
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’)
- 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
/* 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"
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
ABC
HOW TO REPORT prime n:
REPORT n>=2 AND NO d IN {2..floor root n} HAS n mod d = 0
HOW TO RETURN digit.sum n:
SELECT:
n<10: RETURN n
ELSE: RETURN (n mod 10) + digit.sum floor (n/10)
HOW TO REPORT additive.prime n:
REPORT prime n AND prime digit.sum n
PUT 0 IN n
FOR i IN {1..499}:
IF additive.prime i:
WRITE i>>4
PUT n+1 IN n
IF n mod 10 = 0: WRITE /
WRITE /
WRITE "There are `n` additive primes less than 500."/
- 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.
Action!
;;; find some additive primes - primes whose digit sum is also prime
;;; Library: Action! Sieve of Eratosthenes
INCLUDE "H6:SIEVE.ACT"
PROC Main()
DEFINE MAX_PRIME = "500"
BYTE ARRAY primes(MAX_PRIME)
CARD n, digitSum, v, count
Sieve(primes,MAX_PRIME)
count = 0
FOR n = 1 TO MAX_PRIME - 1 DO
IF primes( n ) THEN
digitSum = 0
v = n
WHILE v > 0 DO
digitSum ==+ v MOD 10
v ==/ 10
OD
IF primes( digitSum ) THEN
IF n < 100 THEN
Put(' )
IF n < 10 THEN Put(' ) FI
FI
Put(' )PrintI( n )
count ==+ 1
IF count MOD 20 = 0 THEN PutE() FI
FI
FI
OD
PutE()Print( "Found " )PrintI( count )Print( " additive primes below " )PrintI( MAX_PRIME + 1 )PutE()
RETURN
- 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 501
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;
- 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
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 ) ) );
print( ( " additive primes below ", whole( UPB prime + 1, 0 ), newline ) )
END
- 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
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.
- 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
((+⌿(4/10)⊤P)∊P)/P←(~P∊P∘.×P)/P←1↓⍳500
- 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
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}
- Output:
{|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}
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"
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
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"]
- 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
# 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)
}
- 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
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
- 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
Applesoft BASIC
0 E = 500
1 F = E - 1:L = LEN ( STR$ (F)) + 1: FOR I = 2 TO L:S$ = S$ + CHR$ (32): NEXT I: DIM P(E):P(0) = - 1:P(1) = - 1: FOR I = 2 TO SQR (F): IF NOT P(I) THEN FOR J = I * 2 TO E STEP I:P(J) = - 1: NEXT J
2 NEXT I: FOR I = B TO F: IF NOT P(I) THEN GOSUB 4
3 NEXT I: PRINT : PRINT N" ADDITIVE PRIMES FOUND BELOW "E;: END
4 S = 0: IF I THEN FOR J = I TO 0 STEP 0:J1 = INT (J / 10):S = S + (J - J1 * 10):J = J1: NEXT J
5 IF NOT P(S) THEN N = N + 1: PRINT RIGHT$ (S$ + STR$ (I),L);
6 RETURN
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
BASIC256
print "Prime", "Digit Sum"
for i = 2 to 499
if isprime(i) then
s = digSum(i)
if isPrime(s) then print i, s
end if
next i
end
function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
function digsum(n)
s = 0
while n
s += n mod 10
n /= 10
end while
return s
end function
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)
$)
- 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
#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 */
- 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++
#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";
}
- 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.
C#
internal class Program
{
private static void Main(string[] args)
{
long primeCandidate = 1;
long additivePrimeCount = 0;
Console.WriteLine("Additive Primes");
while (primeCandidate < 500)
{
if (IsAdditivePrime(primeCandidate))
{
additivePrimeCount++;
Console.Write($"{primeCandidate,-3} ");
if (additivePrimeCount % 10 == 0)
{
Console.WriteLine();
}
}
primeCandidate++;
}
Console.WriteLine();
Console.WriteLine($"Found {additivePrimeCount} additive primes less than 500");
}
private static bool IsAdditivePrime(long number)
{
if (IsPrime(number) && IsPrime(DigitSum(number)))
{
return true;
}
return false;
}
private static bool IsPrime(long number)
{
if (number < 2)
{
return false;
}
if (number % 2 == 0)
{
return number == 2;
}
if (number % 3 == 0)
{
return number == 3;
}
int delta = 2;
long k = 5;
while (k * k <= number)
{
if (number % k == 0)
{
return false;
}
k += delta;
delta = 6 - delta;
}
return true;
}
private static long DigitSum(long n)
{
long sum = 0;
while (n > 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
}
- Output:
Additive Primes 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
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
- 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
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).
- 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
(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)))) )
- 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
# 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}."
- 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.
Dart
import 'dart:math';
void main() {
const limit = 500;
print('Additive primes less than $limit :');
int count = 0;
for (int n = 1; n < limit; ++n) {
if (isPrime(digit_sum(n)) && isPrime(n)) {
print(' $n');
++count;
}
}
print('$count additive primes found.');
}
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) return false;
}
return true;
}
int digit_sum(int n) {
int sum = 0;
for (int m = n; m > 0; m ~/= 10) sum += m % 10;
return sum;
}
Delphi
Many Rosette Code problems have similar operations. This problem was solved using subroutines that were written and used for other problems. Instead of packing all the operations in a single block of code, this example shows the advantage of breaking operations into separate modules that aids in code resuse.
{These routines would normally be in libraries but are shown here for clarity}
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function SumDigits(N: integer): integer;
{Sum the integers in a number}
var T: integer;
begin
Result:=0;
repeat
begin
T:=N mod 10;
N:=N div 10;
Result:=Result+T;
end
until N<1;
end;
procedure ShowDigitSumPrime(Memo: TMemo);
var N,Sum,Cnt: integer;
var NS,S: string;
begin
Cnt:=0;
S:='';
for N:=1 to 500-1 do
if IsPrime(N) then
begin
Sum:=SumDigits(N);
if IsPrime(Sum) then
begin
Inc(Cnt);
S:=S+Format('%6d',[N]);
if (Cnt mod 8)=0 then S:=S+CRLF;
end;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count = '+IntToStr(Cnt));
end;
- 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 Elapsed Time: 2.812 ms.
Delphi
See Pascal.
Draco
proc sieve([*] bool prime) void:
word max, p, c;
max := dim(prime,1)-1;
prime[0] := false;
prime[1] := false;
for p from 2 upto max do prime[p] := true od;
for p from 2 upto max/2 do
for c from p*2 by p upto max do
prime[c] := false
od
od
corp
proc digit_sum(word num) byte:
byte sum;
sum := 0;
while
sum := sum + num % 10;
num := num / 10;
num /= 0
do od;
sum
corp
proc main() void:
word MAX = 500;
word p, n;
[MAX]bool prime;
sieve(prime);
n := 0;
for p from 2 upto MAX-1 do
if prime[p] and prime[digit_sum(p)] then
write(p:4);
n := n + 1;
if n % 20 = 0 then writeln() fi
fi
od;
writeln();
writeln("There are ", n, " additive primes below ", MAX)
corp
- 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
EasyLang
func prime n .
if n mod 2 = 0 and n > 2
return 0
.
i = 3
sq = sqrt n
while i <= sq
if n mod i = 0
return 0
.
i += 2
.
return 1
.
func digsum n .
while n > 0
sum += n mod 10
n = n div 10
.
return sum
.
for i = 2 to 500
if prime i = 1
s = digsum i
if prime s = 1
write i & " "
.
.
.
print ""
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).
- 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#)
// 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 ""
- 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
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
- 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
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);
- 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
: 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
- 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.
#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
- 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
Free Pascal
Using Sieve of Eratosthenes to find all primes upto 500, then go through the list, sum digits and check for prime
Program AdditivePrimes;
Const max_number = 500;
Var is_prime : array Of Boolean;
Procedure sieve(Var arr: Array Of boolean );
{use Sieve of Eratosthenes to find all primes to max number}
Var i,j : NativeUInt;
Begin
For i := 2 To high(arr) Do
arr[i] := True; // set all bits to be True
For i := 2 To high(arr) Do
Begin
If (arr[i]) Then
For j := 2 To (high(arr) Div i) Do
arr[i * j] := False;
End;
End;
Function GetSumOfDigits(num: NativeUInt): longint;
{calcualte the sum of digits of a number}
Var
sum : longint = 0;
dummy: NativeUInt;
Begin
Repeat
dummy := num;
num := num Div 10;
Inc(sum, dummy - (num SHL 3 + num SHL 1));
Until num < 1;
GetSumOfDigits := sum;
End;
Var x : NativeUInt = 2; {first prime}
counter : longint = 0;
Begin
setlength(is_prime,max_number); //set length of array to max_number
Sieve(is_prime); //apply Sieve
{since 2 is the only even prime, let's do it separate}
If is_prime[x] And is_prime[GetSumOfDigits(x)] Then
Begin
write(x:4);
inc(counter);
End;
inc(x);
While x < max_number Do
Begin
If is_prime[x] And is_prime[GetSumOfDigits(x)] Then
Begin
if counter mod 10 = 0 then writeln();
write(x:4);
inc(counter);
End;
inc(x,2);
End;
writeln();
writeln();
writeln(counter,' additive primes found.');
End.
- 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.
Frink
vals = toArray[select[primes[2, 500], {|x| isPrime[sum[integerDigits[x]]]}]]
println[formatTable[columnize[vals, 10]]]
println["\n" + length[vals] + " values found."]
- 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 values found.
FutureBasic
local fn IsPrime( n as NSUInteger ) as BOOL
NSUInteger i
BOOL result = YES
if ( n < 2 ) then exit fn = NO
for i = 2 to n + 1
if ( i * i <= n ) and ( n mod i == 0 )
exit fn = NO
end if
next
end fn = result
local fn DigSum( n as NSUInteger ) as NSUInteger
NSUInteger s = 0
while ( n > 0 )
s += ( n mod 10 )
n /= 10
wend
end fn = s
void local fn AdditivePrimes( n as NSUInteger )
NSUInteger i, s = 0, counter = 0
printf @"Additive Primes:"
for i = 2 to n
if ( fn IsPrime(i) ) and ( fn IsPrime( fn DigSum(i) ) )
s++
printf @"%4ld \b", i : counter++
if counter == 10 then counter = 0 : print
end if
next
printf @"\n\nFound %lu additive primes less than %lu.", s, n
end fn
fn AdditivePrimes( 500 )
HandleEvents
- Output:
Additive Primes: 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.
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
Test case 1. Write a program to determine all additive primes less than 500.
Test case 2. Show the number of additive primes.
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)
}
- 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
(#~ 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
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;
}
}
- 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
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] + .;
The task
# 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."))
- 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.
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
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
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
- 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
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")
}
- 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
#!/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
- 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
Lambdatalk
{def isprime
{def isprime.loop
{lambda {:n :m :i}
{if {> :i :m}
then true
else {if {= {% :n :i} 0}
then false
else {isprime.loop :n :m {+ :i 2}}
}}}}
{lambda {:n}
{if {or {= :n 2} {= :n 3} {= :n 5} {= :n 7}}
then true
else {if {or {< : n 2} {= {% :n 2} 0}}
then false
else {isprime.loop :n {sqrt :n} 3}
}}}}
-> isprime
{def digit.sum
{def digit.sum.loop
{lambda {:n :sum}
{if {> :n 0}
then {digit.sum.loop {floor {/ :n 10}}
{+ :sum {% :n 10}}}
else :sum}}}
{lambda {:n}
{digit.sum.loop :n 0}}}
-> digit.sum
{S.replace \s by space in
{S.map {lambda {:i}
{if {and {isprime :i}
{isprime {digit.sum :i}}}
then :i
else}}
{S.serie 2 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
i.e 54 additive primes until 500.
langur
val isPrime = fn(i) {
i == 2 or i > 2 and
not any(fn x: i div x, pseries(2 .. i ^/ 2))
}
val sumDigits = fn i: fold(fn{+}, s2n(string(i)))
writeln "Additive primes less than 500:"
var cnt = 0
for i in [2] ~ series(3..500, 2) {
if isPrime(i) and isPrime(sumDigits(i)) {
write "{{i:3}} "
cnt += 1
if cnt div 10: writeln()
}
}
writeln "\n\n{{cnt}} additive primes found.\n"
- 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.
Lua
This task uses primegen
from: Extensible_prime_generator#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)
- 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
ClearAll[AdditivePrimeQ]
AdditivePrimeQ[n_Integer] := PrimeQ[n] \[And] PrimeQ[Total[IntegerDigits[n]]]
Select[Range[500], AdditivePrimeQ]
- 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}
Maxima
/* Function that returns a list of digits given a nonnegative integer */
decompose(num) := block([digits, remainder],
digits: [],
while num > 0 do
(remainder: mod(num, 10),
digits: cons(remainder, digits),
num: floor(num/10)),
digits
)$
/* Routine that extracts from primes between 2 and 500, inclusive, the additive primes */
block(
primes(2,500),
sublist(%%,lambda([x],primep(apply("+",decompose(x))))));
/* Number of additive primes in the rank */
length(%);
- 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
MiniScript
isPrime = function(n)
if n <= 3 then return n > 1
if n % 2 == 0 or n % 3 == 0 then return false
i = 5
while i ^ 2 <= n
if n % i == 0 or n % (i + 2) == 0 then return false
i += 6
end while
return true
end function
digitSum = function(n)
sum = 0
while n > 0
sum += n % 10
n = floor(n / 10)
end while
return sum
end function
additive = []
for i in range(2, 500)
if isPrime(i) and isPrime(digitSum(i)) then additive.push(i)
end for
print "There are " + additive.len + " additive primes under 500."
print additive
- Output:
miniscript.exe additive-prime.ms There are 54 additive 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]
Miranda
main :: [sys_message]
main = [Stdout (table 5 10 nums), Stdout countmsg]
where nums = filter additive_prime [1..500]
countmsg = "Found " ++ show (#nums) ++ " additive primes < 500\n"
table :: num->num->[num]->[char]
table w c ls = lay [concat (map (rjustify w . show) l) | l <- split c ls]
split :: num->[*]->[[*]]
split n ls = [ls], if #ls < n
= take n ls:split n (drop n ls), otherwise
additive_prime :: num->bool
additive_prime n = prime (dsum n) & prime n
dsum :: num->num
dsum n = n, if n<10
= n mod 10 + dsum (n div 10), otherwise
prime :: num->bool
prime n = n>=2 & #[d | d<-[2..entier (sqrt n)]; n mod d=0] = 0
- 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
Modula-2
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.
- 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.
Modula-3
MODULE AdditivePrimes EXPORTS Main;
IMPORT SIO,Fmt;
CONST
Max = 500;
VAR
Count:CARDINAL := 0;
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 J: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;
INC(J,I)
END
END
END;
END Sieve;
BEGIN
Sieve();
FOR N := 2 TO Max DO
IF Prime[N] AND Prime[DigitSum(N)] THEN
SIO.PutText(Fmt.F("%4s",Fmt.Int(N)));
INC(Count);
IF Count MOD 10 = 0 THEN SIO.Nl() END
END
END;
SIO.PutText(Fmt.F("\nThere are %s additive primes less than %s.\n",
Fmt.Int(Count),Fmt.Int(Max)));
END AdditivePrimes.
- 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
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
- 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
Oberon-07
MODULE AdditivePrimes;
IMPORT
Out;
CONST
Max = 500;
VAR
Count, n :INTEGER;
Prime :ARRAY Max + 1 OF BOOLEAN;
PROCEDURE DigitSum( n :INTEGER ):INTEGER;
VAR result :INTEGER;
BEGIN
result := 0;
IF n < 10 THEN result := n
ELSE result := ( n MOD 10 ) + DigitSum( n DIV 10 )
END
RETURN result
END DigitSum;
PROCEDURE Sieve;
VAR i, j :INTEGER;
BEGIN
Prime[ 0 ] := FALSE; Prime[ 1 ] := FALSE;
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
Sieve;
FOR n := 2 TO Max DO
IF Prime[ n ] & Prime[ DigitSum( n ) ] THEN
Out.Int( n, 4 );
Count := Count + 1;
IF Count MOD 20 = 0 THEN Out.Ln END
END
END;
Out.Ln;Out.String( "There are " );Out.Int( Count, 1 );
Out.String( " additive primes less than " );Out.Int( Max, 1 );
Out.String( "." );Out.Ln
END AdditivePrimes.
- 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.
OCaml
let rec digit_sum n =
if n < 10 then n else n mod 10 + digit_sum (n / 10)
let is_prime n =
let rec test x =
let q = n / x in x > q || x * q <> n && n mod (x + 2) <> 0 && test (x + 6)
in if n < 5 then n lor 1 = 3 else n land 1 <> 0 && n mod 3 <> 0 && test 5
let is_additive_prime n =
is_prime n && is_prime (digit_sum n)
let () =
Seq.ints 0 |> Seq.take_while ((>) 500) |> Seq.filter is_additive_prime
|> Seq.iter (Printf.printf " %u") |> print_newline
- 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
Pari/GP
This is a good task for demonstrating several different ways to approach a simple problem.
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]
- 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.
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.
- 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
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);
- 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
Phixmonti
/# Rosetta Code problem: http://rosettacode.org/wiki/Additive_primes
by Galileo, 05/2022 #/
include ..\Utilitys.pmt
def isprime
dup 1 <= if drop false
else dup 2 == not if
( dup sqrt 2 swap ) for
over swap mod not if drop false exitfor endif
endfor
endif
endif
false == not
enddef
def digitsum
0 swap dup 0 > while dup 10 mod rot + swap 10 / int dup 0 > endwhile
drop
enddef
0 500 for
dup isprime over digitsum isprime and if print " " print 1 + else drop endif
endfor
"Additive primes found: " print 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 Additive primes found: 54 === Press any key to exit ===
Picat
main =>
PCount = 0,
foreach (I in 2..499)
if prime(I) && prime(sum_digits(I)) then
PCount := PCount + 1,
printf("%4d ", I)
end
end,
printf("\n\n%d additive primes found.\n", PCount).
sum_digits(N) = S =>
S = sum([ord(C)-ord('0') : C in to_string(N)]).
- 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.
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) )
- 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
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 :
- 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.
/* 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;
- 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
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--;
}
}
}
}
- 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
#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()
- 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
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()
- 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.
500 eratosthenes
[]
500 times
[ i^ isprime if
[ i^ 10 digitsum
isprime if
[ i^ join ] ] ]
dup echo cr cr
size echo say " additive primes found."
- 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.
R
digitsum <- function(x) sum(floor(x / 10^(0:(nchar(x) - 1))) %% 10)
is.prime <- function(n) n == 2L || all(n %% 2L:max(2,floor(sqrt(n))) != 0)
range_int <- 2:500
v <- sapply(range_int, \(x) is.prime(x) && is.prime(digitsum(x)))
cat(paste("Found",length(range_int[v]),"additive primes less than 500"))
print(range_int[v])
- Output:
Found 54 additive primes less than 500 [1] 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 [24] 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 [47] 409 421 443 449 461 463 467 487
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)
- 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
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 }
- 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
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
Uses primes
defined in https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Red.
REXX
/*REXX program counts/displays the number of additive primes less than 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=5 /*width of a number in any column. */
title= 'additive primes that are < 'commas(n)
If cols>0 Then Say ' index ¦'center(title,cols*(w+1)+1)
If cols>0 Then Say '-------+'center('' ,cols*(w+1)+1,'-')
found=0
ol='' /*a list of additive primes (so far). */
idx=1
Do j=1 By 1
p=p.j /*obtain the Jth prime. */
If p>n Then Leave /* no more needed */
_=sumDigs(p)
If !._ Then Do
found=found+1 /*bump the count of additive primes. */
c=commas(p) /*maybe add commas To the number. */
ol=ol right(c,max(w,length(c))) /*add additive prime--?list,allow big# */
If words(ol)=10 Then Do /* a line is complete */
Say center(idx,7)'¦' substr(ol,2) /*display what we have so far (cols). */
ol='' /* prepare for next line */
idx=idx+10
End
End
End /*j*/
If ol\=='' Then
Say center(idx,7)'¦' substr(ol,2) /*possible display residual output. */
If cols>0 Then
Say '--------'center('',cols*(w+1)+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
pl=2 3 5 7 11 13
!.=0
Do np=1 By 1 While pl<>''
Parse Var pl p pl
p.np=p
sq.np=p*p
!.p=1
End
np=np-1
Do j=p.np+2 by 2 While j<n
Parse Var j '' -1 _ /*obtain the last digit of the J var.*/
If _==5 Then Iterate
If j// 3==0 Then Iterate
If j// 7==0 Then Iterate
If j//11==0 Then Iterate
Do k=6 By 1 While sq.k<=j /*divide J by other primes <=sqrt(j) */
If j//p.k==0 Then Iterate j /* not prime - try next */
End /*k*/
np=np+1 /*bump prime count; assign prime & flag*/
p.np=j
sq.np=j*j
!.j=1
End /*j*/
Return
- 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
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
- 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...
RPL
≪ →STR 0 1 3 PICK SIZE FOR j OVER j DUP SUB STR→ + NEXT NIP ≫ '∑DIGITS' STO ≪ { } 1 DO NEXTPRIME IF DUP ∑DIGITS ISPRIME? THEN SWAP OVER + SWAP END UNTIL DUP 500 ≥ END DROP DUP SIZE ≫ 'TASK' STO
- Output:
2: { 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 } 1: 54
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}."
- 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
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}");
}
- 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)
// [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}");
}
- 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
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}")
- 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
$ 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;
- 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.
SETL
program additive_primes;
loop for i in [i : i in [1..499] | additive_prime i] do
nprint(lpad(str i, 4));
if (n +:= 1) mod 10 = 0 then
print;
end if;
end loop;
print;
print("There are " + str n + " additive primes less than 500.");
op additive_prime(n);
return prime n and prime digitsum n;
end op;
op prime(n);
return n>=2 and not exists d in {2..floor sqrt n} | n mod d = 0;
end op;
op digitsum(n);
loop while n>0;
s +:= n mod 10;
n div:= 10;
end loop;
return s;
end op;
end program;
- 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.
Sidef
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
})
- 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
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
- 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
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.")
- 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.
uBasic/4tH
print "Prime", "Digit Sum"
for i = 2 to 499
if func(_isPrime(i)) then
s = func(_digSum(i))
if func(_isPrime(s)) then
print i, s
endif
endif
next
end
_isPrime
param (1)
local (1)
if a@ < 2 then return (0)
if a@ % 2 = 0 then return (a@ = 2)
if a@ % 3 = 0 then return (a@ = 3)
b@ = 5
do while (b@ * b@) < (a@ + 1)
if a@ % b@ = 0 then unloop : return (0)
b@ = b@ + 2
loop
return (1)
_digSum
param (1)
local (1)
b@ = 0
do while a@
b@ = b@ + (a@ % 10)
a@ = a@ / 10
loop
return (b@)
- 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 0 OK, 0:176
Uiua
[] # list of primes to be populated
↘2⇡500 # candidates (starting at 2)
# Take the first remaining candidate, which will be prime, save it,
# then remove every candidate that it divides. Repeat until none left.
⍢(▽≠0◿⊃⊢(.↘1)⟜(⊂⊢)|>0⧻)
# Tidy up.
⇌◌
# Build sum of digits of each.
≡(/+≡⋕°⋕)...
# Mask out those that result in non-primes.
⊏⊚±⬚0⊏⊗
# Return values and length.
⧻.
- 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
V (Vlang)
fn is_prime(n int) bool {
if n < 2 {
return false
} else if n%2 == 0 {
return n == 2
} else if n%3 == 0 {
return n == 3
} else {
mut d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
fn sum_digits(nn int) int {
mut n := nn
mut sum := 0
for n > 0 {
sum += n % 10
n /= 10
}
return sum
}
fn main() {
println("Additive primes less than 500:")
mut i := 2
mut count := 0
for {
if is_prime(i) && is_prime(sum_digits(i)) {
count++
print("${i:3} ")
if count%10 == 0 {
println('')
}
}
if i > 2 {
i += 2
} else {
i++
}
if i > 499 {
break
}
}
println("\n\n$count additive primes found.")
}
- 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.
VTL-2
10 M=499
20 :1)=1
30 P=2
40 :P)=0
50 P=P+1
60 #=M>P*40
70 P=2
80 C=P*2
90 :C)=1
110 C=C+P
120 #=M>C*90
130 P=P+1
140 #=M/2>P*80
150 P=2
160 N=0
170 #=:P)*290
180 S=0
190 K=P
200 K=K/10
210 S=S+%
220 #=0<K*200
230 #=:S)*290
240 ?=P
250 $=9
260 N=N+1
270 #=N/10*0+%=0=0*290
280 ?=""
290 P=P+1
300 #=M>P*170
310 ?=""
320 ?="There are ";
330 ?=N
340 ?=" additive primes below ";
350 ?=M+1
- 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
Wren
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.")
- 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
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.
");
]
- 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.
Yabasic
// Rosetta Code problem: http://rosettacode.org/wiki/Additive_primes
// by Galileo, 06/2022
limit = 500
dim flags(limit)
for i = 2 to limit
for k = i*i to limit step i
flags(k) = 1
next
if flags(i) = 0 primes$ = primes$ + str$(i) + " "
next
dim prim$(1)
n = token(primes$, prim$())
for i = 1 to n
sum = 0
num$ = prim$(i)
for j = 1 to len(num$)
sum = sum + val(mid$(num$, j, 1))
next
if instr(primes$, str$(sum) + " ") print prim$(i), " "; : count = count + 1
next
print "\nFound: ", count
- 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 ---Program done, press RETURN---
- Programming Tasks
- Prime Numbers
- 11l
- AArch64 Assembly
- ABC
- Action!
- Action! Sieve of Eratosthenes
- Ada
- ALGOL 68
- ALGOL 68-primes
- ALGOL W
- APL
- AppleScript
- ARM Assembly
- Arturo
- AWK
- BASIC
- Applesoft BASIC
- BASIC256
- BCPL
- C
- C++
- C sharp
- CLU
- COBOL
- Common Lisp
- Crystal
- Dart
- Delphi
- SysUtils,StdCtrls
- Draco
- EasyLang
- Erlang
- F Sharp
- Factor
- Fermat
- Forth
- FreeBASIC
- Free Pascal
- Frink
- FutureBasic
- Fōrmulæ
- Go
- J
- Java
- Jq
- Haskell
- Julia
- Kotlin
- Ksh
- Lambdatalk
- Langur
- Lua
- Mathematica
- Wolfram Language
- Maxima
- MiniScript
- Miranda
- Modula-2
- Modula-3
- Nim
- Oberon-07
- OCaml
- Pari/GP
- Pascal
- Perl
- Ntheory
- Phix
- Phixmonti
- Picat
- PicoLisp
- PILOT
- PL/I
- PL/M
- Polyglot:PL/I and PL/M
- Processing
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- Red
- REXX
- Ring
- RPL
- Ruby
- Rust
- Sage
- Seed7
- SETL
- Sidef
- TSE SAL
- Swift
- UBasic/4tH
- Uiua
- V (Vlang)
- VTL-2
- Wren
- Wren-math
- Wren-fmt
- XPL0
- Yabasic