Additive primes
- 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.
ALGOL W
<lang algolw>begin % find some additive primes - primes whose digit sum is also prime %
% sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for pr := i * i step ii until n do p( pr ) := false
end for_i ;
end Eratosthenes ;
integer MAX_NUMBER;
MAX_NUMBER := 500;
begin
logical array prime( 1 :: MAX_NUMBER );
integer aCount;
% sieve the primes to MAX_NUMBER %
Eratosthenes( prime, MAX_NUMBER );
% find the primes that are additive primes %
aCount := 0;
for i := 1 until MAX_NUMBER - 1 do begin
if prime( i ) then begin
integer dSum, v;
v := i;
dSum := 0;
while v > 0 do begin
dSum := dSum + v rem 10;
v := v div 10
end while_v_gt_0 ;
if prime( dSum ) then begin
writeon( i_w := 4, s_w := 0, " ", i );
aCount := aCount + 1;
if aCount rem 20 = 0 then write()
end if_prime_dSum
end if_prime_i
end for_i ;
write( i_w := 1, s_w := 0, "Found ", aCount, " additive primes below ", MAX_NUMBER )
end
end.</lang>
- Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 Found 54 additive primes below 500
APL
<lang APL>((+⌿(4/10)⊤P)∊P)/P←(~P∊P∘.×P)/P←1↓⍳500</lang>
- Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283
311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487
AppleScript
<lang applescript>on sieveOfEratosthenes(limit)
script o
property numberList : {missing value}
end script
repeat with n from 2 to limit
set end of o's numberList to n
end repeat
repeat with position from 2 to (limit ^ 0.5) div 1
if (item position of o's numberList is not missing value) then
repeat with multiple from position * position to limit by position
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 additivePrimes(limit)
script o
property primes : sieveOfEratosthenes(limit)
property additives : {}
end script
repeat with p in o's primes
set sum to p mod 10
set n to p div 10
repeat until (n = 0)
set sum to sum + n mod 10
set n to n div 10
end repeat
if (sum 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 {additivePrimesBelow500:it, numberThereof:count}</lang>
- Output:
<lang applescript>{additivePrimesBelow500:{2, 3, 5, 7, 11, 23, 29, 41, 43, 47, 61, 67, 83, 89, 101, 113, 131, 137, 139, 151, 157, 173, 179, 191, 193, 197, 199, 223, 227, 229, 241, 263, 269, 281, 283, 311, 313, 317, 331, 337, 353, 359, 373, 379, 397, 401, 409, 421, 443, 449, 461, 463, 467, 487}, numberThereof:54}</lang>
AWK
<lang AWK>
- syntax: GAWK -f ADDITIVE_PRIMES.AWK
BEGIN {
start = 1
stop = 500
for (i=start; i<=stop; i++) {
if (is_prime(i) && is_prime(sum_digits(i))) {
printf("%4d%1s",i,++count%10?"":"\n")
}
}
printf("\nAdditive primes %d-%d: %d\n",start,stop,count)
exit(0)
} function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
} function sum_digits(n, i,sum) {
for (i=1; i<=length(n); i++) {
sum += substr(n,i,1)
}
return(sum)
} </lang>
- Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 Additive primes 1-500: 54
BCPL
<lang bcpl>get "libhdr" manifest $( limit = 500 $)
let dsum(n) =
n=0 -> 0, dsum(n/10) + n rem 10
let sieve(prime, n) be $( 0!prime := false
1!prime := false
for i=2 to n do i!prime := true
for i=2 to n/2
if i!prime
$( let j=i+i
while j<=n
$( j!prime := false
j := j+i
$)
$)
$)
let additive(prime, n) = n!prime & dsum(n)!prime
let start() be $( let prime = vec limit
let num = 0
sieve(prime, limit)
for i=2 to limit
if additive(prime,i)
$( writed(i,5)
num := num + 1
if num rem 10 = 0 then wrch('*N')
$)
writef("*N*NFound %N additive primes < %N.*N", num, limit)
$)</lang>
- Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 Found 54 additive primes < 500.
C++
<lang cpp>#include <iomanip>
- include <iostream>
bool is_prime(unsigned int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (unsigned int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
unsigned int digit_sum(unsigned int n) {
unsigned int sum = 0;
for (; n > 0; n /= 10)
sum += n % 10;
return sum;
}
int main() {
const unsigned int limit = 500;
std::cout << "Additive primes less than " << limit << ":\n";
unsigned int count = 0;
for (unsigned int n = 1; n < limit; ++n) {
if (is_prime(digit_sum(n)) && is_prime(n)) {
std::cout << std::setw(3) << n;
if (++count % 10 == 0)
std::cout << '\n';
else
std::cout << ' ';
}
}
std::cout << '\n' << count << " additive primes found.\n";
}</lang>
- Output:
Additive primes less than 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 54 additive primes found.
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Additive Primes. Nigel Galloway: March 22nd., 2021 let rec fN g=function n when n<10->n+g |n->fN(g+n%10)(n/10) primes32()|>Seq.takeWhile((>)500)|>Seq.filter(fN 0>>isPrime)|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487
Factor
<lang factor>USING: formatting grouping io kernel math math.primes prettyprint sequences ;
- sum-digits ( n -- sum )
0 swap [ 10 /mod rot + swap ] until-zero ;
499 primes-upto [ sum-digits prime? ] filter [ 9 group simple-table. nl ] [ length "Found %d additive primes < 500.\n" printf ] bi</lang>
- Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 Found 54 additive primes < 500.
Forth
<lang forth>: prime? ( n -- ? ) here + c@ 0= ;
- notprime! ( n -- ) here + 1 swap c! ;
- prime_sieve ( n -- )
here over erase
0 notprime!
1 notprime!
2
begin
2dup dup * >
while
dup prime? if
2dup dup * do
i notprime!
dup +loop
then
1+
repeat
2drop ;
- digit_sum ( u -- u )
dup 10 < if exit then 10 /mod recurse + ;
- print_additive_primes ( n -- )
." Additive primes less than " dup 1 .r ." :" cr
dup prime_sieve
0 swap
1 do
i prime? if
i digit_sum prime? if
i 3 .r
1+ dup 10 mod 0= if cr else space then
then
then
loop
cr . ." additive primes found." cr ;
500 print_additive_primes bye</lang>
- Output:
Additive primes less than 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 54 additive primes found.
FreeBASIC
As with the other special primes tasks, use one of the primality testing algorithms as an include. <lang freebasic>#include "isprime.bas"
function digsum( n as uinteger ) as uinteger
dim as uinteger s
while n
s+=n mod 10
n\=10
wend
return s
end function
dim as uinteger s
print "Prime","Digit Sum" for i as uinteger = 2 to 499
if isprime(i) then
s = digsum(i)
if isprime(s) then
print i, s
end if
end if
next i</lang>
- Output:
Prime Digit Sum 2 2 3 3 5 5 7 7 11 2 23 5 29 11 41 5 43 7 47 11 61 7 67 13 83 11 89 17 101 2 113 5 131 5 137 11 139 13 151 7 157 13 173 11 179 17 191 11 193 13 197 17 199 19 223 7 227 11 229 13 241 7 263 11 269 17 281 11 283 13 311 5 313 7 317 11 331 7 337 13 353 11 359 17 373 13 379 19 397 19 401 5 409 13 421 7 443 11 449 17 461 11 463 13 467 17 487 19
Go
<lang go>package main
import "fmt"
func isPrime(n int) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
default:
d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
func sumDigits(n int) int {
sum := 0
for n > 0 {
sum += n % 10
n /= 10
}
return sum
}
func main() {
fmt.Println("Additive primes less than 500:")
i := 2
count := 0
for {
if isPrime(i) && isPrime(sumDigits(i)) {
count++
fmt.Printf("%3d ", i)
if count%10 == 0 {
fmt.Println()
}
}
if i > 2 {
i += 2
} else {
i++
}
if i > 499 {
break
}
}
fmt.Printf("\n\n%d additive primes found.\n", count)
}</lang>
- Output:
Additive primes less than 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 54 additive primes found.
Julia
<lang julia>using Primes
let
p = primesmask(500)
println("Additive primes under 500:")
pcount = 0
for i in 2:499
if p[i] && p[sum(digits(i))]
pcount += 1
print(lpad(i, 4), pcount % 20 == 0 ? "\n" : "")
end
end
println("\n\n$pcount additive primes found.")
end
</lang>
- Output:
Erdős primes under 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 54 additive primes found.
Nim
<lang Nim>import math, strutils
const N = 499
- Sieve of Erathostenes.
var composite: array[2..N, bool] # Initialized to false, ie. prime.
for n in 2..sqrt(N.toFloat).int:
if not composite[n]:
for k in countup(n * n, N, n):
composite[k] = true
func digitSum(n: Positive): Natural =
## Compute sum of digits. var n = n.int while n != 0: result += n mod 10 n = n div 10
echo "Additive primes less than 500:"
var count = 0
for n in 2..N:
if not composite[n] and not composite[digitSum(n)]: inc count stdout.write ($n).align(3) stdout.write if count mod 10 == 0: '\n' else: ' '
echo()
echo "\nNumber of additive primes found: ", count</lang>
- Output:
Additive primes less than 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 Number of additive primes found: 54
Perl
<lang perl>use strict; use warnings; use ntheory 'is_prime'; use List::Util <sum max>;
sub pp {
my $format = ('%' . (my $cw = 1+length max @_) . 'd') x @_;
my $width = ".{@{[$cw * int 60/$cw]}}";
(sprintf($format, @_)) =~ s/($width)/$1\n/gr;
}
my($limit, @ap) = 500; is_prime($_) and is_prime(sum(split ,$_)) and push @ap, $_ for 1..$limit;
print @ap . " additive primes < $limit:\n" . pp(@ap);</lang>
- Output:
54 additive primes < 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487
Phix
function additive(integer p) return is_prime(sum(sq_sub(sprint(p),'0'))) end function sequence res = filter(get_primes_le(500),additive) string r = join(shorten(apply(res,sprint),"",6)) printf(1,"%d additive primes found: %s\n",{length(res),r})
- Output:
54 additive primes found: 2 3 5 7 11 23 ... 443 449 461 463 467 487
Raku
<lang perl6>unit sub MAIN ($limit = 500); say "{+$_} additive primes < $limit:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}",
with ^$limit .grep: { .is-prime and .comb.sum.is-prime }</lang>
- Output:
54 additive primes < 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487
REXX
<lang rexx>/*REXX program counts/displays the number of additive primes under a specified number N.*/ parse arg n cols . /*get optional number of primes to find*/ if n== | n=="," then n= 500 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /* " " " " " */ call genP n /*generate all primes under N. */ w= 10 /*width of a number in any column. */ if cols>0 then say ' index │'center(" additive primes that are < " n, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') Aprimes= 0; idx= 1 /*initialize # of additive primes & idx*/ $= /*a list of additive primes (so far). */
do j=2 until j>=n; if \!.j then iterate /*Is J not a prime? No, then skip it.*/
_= sumDigs(j); if \!._ then iterate /*is sum of J's digs a prime? No, skip.*/
Aprimes= Aprimes + 1 /*bump the count of additive primes. */
if cols==0 then iterate /*Build the list (to be shown later)? */
c= commas(j) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add additive prime──►list, allow big#*/
if Aprimes//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'found ' commas(Aprimes) " additive primes < " commas(n) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? sumDigs: parse arg x 1 s 2; do k=2 for length(x)-1; s= s + substr(x,k,1); end; return s /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg n; @.=.; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; #= 7
w= length(n); !.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1
do j=@.7+2 by 2 while j<n /*continue on with the next odd prime. */
parse var j -1 _ /*obtain the last digit of the J var.*/
if _ ==5 then iterate /*is this integer a multiple of five? */
if j // 3 ==0 then iterate /* " " " " " " three? */
/* [↓] divide by the primes. ___ */
do k=4 to # while k*k<=j /*divide J by other primes ≤ √ J */
if j//@.k == 0 then iterate j /*÷ by prev. prime? ¬prime ___ */
end /*k*/ /* [↑] only divide up to √ J */
#= # + 1; @.#= j; !.j= 1 /*bump prime count; assign prime & flag*/
end /*j*/
return</lang>
- output when using the default inputs:
index │ additive primes that are < 500 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 11 23 29 41 43 47 11 │ 61 67 83 89 101 113 131 137 139 151 21 │ 157 173 179 191 193 197 199 223 227 229 31 │ 241 263 269 281 283 311 313 317 331 337 41 │ 353 359 373 379 397 401 409 421 443 449 51 │ 461 463 467 487 found 54 additive primes < 500
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Additive primes are:" + nl
row = 0 limit = 500
for n = 1 to limit
num = 0
if isprime(n)
strn = string(n)
for m = 1 to len(strn)
num = num + number(strn[m])
next
if isprime(num)
row = row + 1
see "" + n + " "
if row%10 = 0
see nl
ok
ok
ok
next
see nl + "found " + row + " additive primes." + nl see "done..." + nl </lang>
- Output:
working... Additive primes are: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 found 54 additive primes. done...
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var sumDigits = Fn.new { |n|
var sum = 0
while (n > 0) {
sum = sum + (n % 10)
n = (n/10).floor
}
return sum
}
System.print("Additive primes less than 500:") var primes = Int.primeSieve(499) var count = 0 for (p in primes) {
if (Int.isPrime(sumDigits.call(p))) {
count = count + 1
Fmt.write("$3d ", p)
if (count % 10 == 0) System.print()
}
} System.print("\n\n%(count) additive primes found.")</lang>
- Output:
Additive primes less than 500: 2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487 54 additive primes found.