Concatenate two primes is also prime
Find and show here when the concatenation of two primes (p1, p2) shown in base ten is also prime, where p1, p2 < 100.
- Task
ALGOL 68
<lang algol68>BEGIN # find primes whose decimal representation is the concatenation of 2 primes #
INT max low prime = 99; # for the task, only need component primes up to 99 #
INT max prime = max low prime * max low prime;
# sieve the primes to max prime #
[ 1 : max prime ]BOOL prime;
prime[ 1 ] := FALSE; prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI
OD;
# construct a list of the primes up to the maximum low prime to consider #
[ 1 : max low prime ]INT low prime;
INT low pos := 0;
FOR i WHILE low pos < UPB low prime DO IF prime[ i ] THEN low prime[ low pos +:= 1 ] := i FI OD;
# find the primes that can be concatenated to form another prime #
[ 1 : max prime ]BOOL concat prime; FOR i TO UPB concat prime DO concat prime[ i ] := FALSE OD;
# note that all possible concatenated primes have at least 2 digits, so the final digit can't be 2 #
# ( or 5 but we don't check that here ) #
FOR i TO UPB low prime WHILE low prime[ i ] <= max low prime DO
INT p1 = low prime[ i ];
FOR j FROM 2 TO UPB low prime WHILE low prime[ j ] <= max low prime DO
INT p2 = low prime[ j ];
INT pc = ( p1 * IF p2 < 10 THEN 10 ELSE 100 FI ) + p2;
concat prime[ pc ] := prime[ pc ]
OD
OD;
# show the concatenated primes #
INT c count := 0;
FOR n TO UPB concat prime DO
IF concat prime[ n ] THEN
print( ( whole( n, -5 ) ) );
IF ( c count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( newline, newline, "Found ", whole( c count, 0 ), " concat primes", newline ) )
END</lang>
- Output:
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 Found 128 concat primes
ALGOL W
The Algol W for loop allows the loop counter values to be specified as a list - as there are only 25 primes below 100, this feature is used here to save looking through the sieve for the low primes. <lang algolw>begin % find primes whose decimal representation is the concatenation of 2 primes %
integer MAX_PRIME;
MAX_PRIME := 99 * 99;
begin
logical array isPrime ( 1 :: MAX_PRIME );
logical array concatPrime ( 1 :: MAX_PRIME );
integer cCount;
% sieve the primes to MAX_PRIME %
isPrime( 1 ) := false; isPrime( 2 ) := true;
for i := 3 step 2 until MAX_PRIME do isPrime( i ) := true;
for i := 4 step 2 until MAX_PRIME do isPrime( i ) := false;
for i := 3 step 2 until truncate( sqrt( MAX_PRIME ) ) do begin
integer ii; ii := i + i;
if isPrime( i ) then for pr := i * i step ii until MAX_PRIME do isPrime( pr ) := false
end for_i ;
% find the concatenated primes, note their final digit can't be 2 or 5 %
for i := 1 until MAX_PRIME do concatPrime( i ) := false;
cCount := 0;
for p1 := 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 do begin
for p2 := 3, 7, 11, 13, 17, 19, 23, 29, 31, 37
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 do begin
integer pc;
pc := ( p1 * ( if p2 < 10 then 10 else 100 ) ) + p2;
concatPrime( pc ) := isPrime( pc )
end for_p2
end for_p1;
% print the concatenated primes %
cCount := 0;
for i := 1 until MAX_PRIME do begin
if concatPrime( i ) then begin
writeon( i_w := 5, s_w := 0, i );
cCount := cCount + 1;
if cCount rem 10 = 0 then write()
end if_concatPrime_i
end for_i;
write();write( i_w := 1, s_w := 0, "Found ", cCount, " concat primes" )
end
end.</lang>
- Output:
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 Found 128 concat primes
AWK
<lang AWK>
- syntax: GAWK -f CONCATENATE_TWO_PRIMES_IS_ALSO_PRIME.AWK
- sorting:
- PROCINFO["sorted_in"] is used by GAWK
- SORTTYPE is used by Thompson Automation's TAWK
BEGIN {
start = 1
stop = 99
for (i=start; i<=stop; i++) {
if (is_prime(i)) {
for (j=start; j<=stop; j++) {
if (is_prime(j)) {
if (is_prime(i j)) {
arr[i j] = ""
}
}
}
}
}
PROCINFO["sorted_in"] = "@ind_num_asc" ; SORTTYPE = 1
for (i in arr) {
printf("%5d%1s",i,++count%10?"":"\n")
}
printf("\nConcatenate two primes is also prime %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)
} </lang>
- Output:
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 Concatenate two primes is also prime 1-99: 128
Factor
<lang factor>USING: formatting grouping io kernel math.parser math.primes present prettyprint sequences sets sorting ;
"Concatenated-pair primes from primes < 100:" print nl 99 primes-upto [ present ] map dup [ append dec> ] cartesian-map concat [ prime? ] filter members natural-sort [ length ] keep 8 group simple-table. "\nFound %d concatenated primes.\n" printf</lang>
- Output:
Concatenated-pair primes from primes < 100: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 Found 128 concatenated primes.
Go
<lang go>package main
import (
"fmt" "rcu" "sort"
)
func main() {
const LIMIT = 99
primes := rcu.Primes(LIMIT)
rmap := make(map[int]bool)
for _, p := range primes {
for _, q := range primes {
var pq int
if q < 10 {
pq = p*10 + q
} else {
pq = p*100 + q
}
if rcu.IsPrime(pq) {
rmap[pq] = true
}
}
}
results := make([]int, len(rmap))
i := 0
for k := range rmap {
results[i] = k
i++
}
sort.Ints(results)
fmt.Println("Two primes under 100 concatenated together to form another prime:")
for i, p := range results {
fmt.Printf("%5s ", rcu.Commatize(p))
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Println("\n\nFound", len(results), "such concatenated primes.")
}</lang>
- Output:
Two primes under 100 concatenated together to form another prime: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1,117 1,123 1,129 1,153 1,171 1,319 1,361 1,367 1,373 1,723 1,741 1,747 1,753 1,759 1,783 1,789 1,913 1,931 1,973 1,979 1,997 2,311 2,341 2,347 2,371 2,383 2,389 2,917 2,953 2,971 3,119 3,137 3,167 3,719 3,761 3,767 3,779 3,797 4,111 4,129 4,153 4,159 4,337 4,373 4,397 4,723 4,729 4,759 4,783 4,789 5,323 5,347 5,923 5,953 6,113 6,131 6,143 6,173 6,197 6,719 6,737 6,761 6,779 7,129 7,159 7,331 7,919 7,937 8,311 8,317 8,329 8,353 8,389 8,923 8,929 8,941 8,971 9,719 9,743 9,767 Found 128 such concatenated primes.
jq
Works with gojq, the Go implementation of jq
Preliminaries <lang jq>def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else {i:23}
| until( (.i * .i) > $n or ($n % .i == 0); .i += 2)
| .i * .i > $n
end;
- Emit an array of primes less than `.`
def primes:
if . < 2 then [] else [2] + [range(3; .; 2) | select(is_prime)] end;
- Pretty-printing
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; </lang> The task <lang jq># Emit [p1,p2] where p1 < p2 < . and the concatenation is prime def concatenative_primes:
primes | range(0;length) as $i | range($i+1;length) as $j | [.[$i], .[$j]], [.[$j], .[$i]] | select( map(tostring) | add | tonumber | is_prime);
[100 | concatenative_primes | join("||")] | (nwise(10) | map(lpad(6)) | join(" "))</lang>
- Output:
2||3 2||11 2||23 2||29 2||41 2||71 2||83 5||3 3||7 7||3 3||11 11||3 3||13 3||17 17||3 19||3 23||3 29||3 3||31 31||3 3||37 37||3 43||3 3||47 3||53 3||59 59||3 61||3 3||67 67||3 3||73 73||3 3||79 3||83 3||89 3||97 5||23 5||41 5||47 5||71 13||7 7||19 19||7 31||7 7||43 7||61 61||7 67||7 7||73 79||7 7||97 97||7 11||17 11||23 23||11 11||29 41||11 11||53 11||71 83||11 13||19 19||13 13||61 61||13 13||67 13||73 17||23 29||17 17||41 17||47 17||53 17||59 17||83 83||17 17||89 19||31 31||19 37||19 67||19 19||73 19||79 79||19 19||97 97||19 23||41 23||47 47||23 53||23 59||23 23||71 23||83 23||89 89||23 41||29 47||29 29||53 29||71 71||29 83||29 89||29 31||37 61||31 31||67 73||31 43||37 37||61 37||67 67||37 37||79 79||37 37||97 41||53 41||59 89||41 61||43 43||73 43||97 97||43 53||47 47||59 47||83 47||89 59||53 83||53 71||59 67||61 61||73 61||97 67||79 97||67
Julia
<lang julia>using Primes
function catprimes()
found, pri = Int[], primes(100)
for x in pri, y in pri
n = x + y * (x < 10 ? 10 : 100)
isprime(n) && push!(found, n)
end
return sort!(unique(found))
end
foreach(p -> print(lpad(last(p), 5), first(p) % 16 == 0 ? "\n" : ""),
catprimes() |> enumerate)
</lang>
- Output:
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767
Nim
<lang Nim>import strutils, sugar
func isPrime(n: Positive): bool =
if n == 1: return false if (n and 1) == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false if n mod (d + 2) == 0: return false inc d, 6 result = true
- List of primes.
const Primes = collect(newSeq, for n in 2..<100: (if n.isPrime: n))
var concatPrimes: set[0..9999] # Using a set to eliminate duplicates and avoid sort. for p1 in Primes:
for p2 in Primes:
let n = p2 + p1 * (if p2 < 10: 10 else: 100)
if n.isPrime:
concatPrimes.incl n
echo "Found $# primes which are a concatenation of two primes below 100:".format(concatPrimes.len) var i = 1 for n in concatPrimes:
stdout.write ($n).align(4), if i mod 16 == 0: '\n' else: ' ' inc i</lang>
- Output:
Found 128 primes which are a concatenation of two primes below 100: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Concatenate_two_primes_is_also_prime use warnings; use ntheory qw( primes is_prime ); use List::Util qw( uniq );
my @primes = @{ primes(100) }; my @valid = uniq sort { $a <=> $b } grep is_prime($_),
map { my $prefix = $_; map "$prefix$_", @primes } @primes;
print @valid . " primes found\n\n@valid\n" =~ s/.{79}\K /\n/gr;</lang>
- Output:
128 primes found 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767
Phix
with javascript_semantics sequence primes = get_primes_le(100), result = {} for i=1 to length(primes) do integer p = primes[i] for j=1 to length(primes) do integer q = primes[j], pq = p*iff(q<10?10:100)+q if is_prime(pq) then result &= pq end if end for end for result = unique(deep_copy(result)) -- (see note) printf(1,"Found %d such primes: %V\n",{length(result),shorten(result,"",5)})
Note: The deep_copy() [for pwa/p2js] on such calls to unique() would be unnecessary were result routine-local, due to automatic pbr, but here that variable is file-level.
While the (human-readable) error message (without it) is deep within sort(), the call stack makes it clear where that call should best go.
- Output:
Found 128 such primes: {23,37,53,73,113,"...",8941,8971,9719,9743,9767}
Raku
Inefficient, but for a limit of 100, who cares? <lang perl6>my @p = ^1e2 .grep: *.is-prime;
say display ( @p X~ @p ).grep( *.is-prime ).unique.sort( +* );
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n") {
cache $list; $title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}</lang>
- Output:
128 matching:
23 37 53 73 113 137 173 193 197 211
223 229 233 241 271 283 293 311 313 317
331 337 347 353 359 367 373 379 383 389
397 433 523 541 547 571 593 613 617 673
677 719 733 743 761 773 797 977 1117 1123
1129 1153 1171 1319 1361 1367 1373 1723 1741 1747
1753 1759 1783 1789 1913 1931 1973 1979 1997 2311
2341 2347 2371 2383 2389 2917 2953 2971 3119 3137
3167 3719 3761 3767 3779 3797 4111 4129 4153 4159
4337 4373 4397 4723 4729 4759 4783 4789 5323 5347
5923 5953 6113 6131 6143 6173 6197 6719 6737 6761
6779 7129 7159 7331 7919 7937 8311 8317 8329 8353
8389 8923 8929 8941 8971 9719 9743 9767
REXX
<lang rexx>/*REXX pgm finds & displays base ten primes P1 & P2, when concatenated, is also a prime.*/ parse arg hip cols . /*obtain optional arguments from the CL*/ if hip== | hip=="," then hip= 100 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ title= ' concatenation of two primes (P1, P2) in base ten that results in a prime, ' ,
" where P1 & P2 are < " commas(hip)
w= 10 /*width of a number in any column. */ if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') a.= 0 /*array of "2cat" primes */
do j=1 for ## /*search through specified primes. */
do k=1 for ##; cat2= @.j || @.k /*create a concatenated prime (base 10)*/
if !.cat2 then a.cat2= 1 /*flag it as being a "2cat" prime. */
end /*k*/ /* [↑] forgoes the need for sorting. */
end /*j*/
found= 0; idx= 1 /*initialize # of primes found; IDX. */ $=; do n=1 by 2 for hip**2%2 /*search for odd "cat2" primes. */
if \a.n then iterate /*search through allowable primes. */
found= found + 1 /*bump the number of primes found. */
if cols<=0 then iterate /*Build the list (to be shown later)? */
c= commas(n) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a prime ──► $ list, allow big #*/
if found//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*n*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(found) title exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " semaphores. */
#= 5; sq.#= @.#**2 /*the square of the highest low prime. */
do j=@.#+2 by 2 to hip**2-1 /*find odd primes from here on. */
parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
if j<hip then ##= # /*find a shortcut for the 1st DO loop. */
end /*j*/; return</lang>
- output when using the default inputs:
index │ concatenation of two primes (P1, P2) in base ten that results in a prime, where P1 & P2 are < 100 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 23 37 53 73 113 137 173 193 197 211 11 │ 223 229 233 241 271 283 293 311 313 317 21 │ 331 337 347 353 359 367 373 379 383 389 31 │ 397 433 523 541 547 571 593 613 617 673 41 │ 677 719 733 743 761 773 797 977 1,117 1,123 51 │ 1,129 1,153 1,171 1,319 1,361 1,367 1,373 1,723 1,741 1,747 61 │ 1,753 1,759 1,783 1,789 1,913 1,931 1,973 1,979 1,997 2,311 71 │ 2,341 2,347 2,371 2,383 2,389 2,917 2,953 2,971 3,119 3,137 81 │ 3,167 3,719 3,761 3,767 3,779 3,797 4,111 4,129 4,153 4,159 91 │ 4,337 4,373 4,397 4,723 4,729 4,759 4,783 4,789 5,323 5,347 101 │ 5,923 5,953 6,113 6,131 6,143 6,173 6,197 6,719 6,737 6,761 111 │ 6,779 7,129 7,159 7,331 7,919 7,937 8,311 8,317 8,329 8,353 121 │ 8,389 8,923 8,929 8,941 8,971 9,719 9,743 9,767 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 128 concatenation of two primes (P1, P2) in base ten that results in a prime, where P1 & P2 are < 100
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "Concatenate two primes is also prime:" + nl row = 0 prime = []
for n = 1 to 100
for m = 1 to 100
ps1 = string(n)
ps2 = string(m)
ps12 = ps1 + ps2
ps21 = ps2 + ps1
p1 = number(ps12)
p2 = number(ps21)
if isprime(n) and isprime(m)
if isprime(p1)
pf = find(prime,p1)
if pf < 1
add(prime,p1)
ok
ok
if isprime(p2)
pf = find(prime,p2)
if pf < 1
add(prime,p2)
ok
ok
ok
next
next
prime = sort(prime) for n = 1 to len(prime)
row++
see "" + prime[n] + " "
if row%10 = 0
see nl
ok
next
see nl + "Found " + row + " prime numbers" + nl see "done..." + nl </lang>
- Output:
working... Concatenate two primes is also prime: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 Found 128 prime numbers done...
Sidef
<lang ruby>var upto = 100 var arr = upto.primes var base = 10
arr = arr.map {|p|
var d = p.digits(base);
arr.map {|q| [q.digits(base)..., d...].digits2num(base) }.grep { .is_prime }
}.flat.uniq.sort
say "Concatenated primes from primes p,q <= #{upto}:"
arr.each_slice(10, {|*a|
say a.map { '%6s' % _ }.join(' ')
})
say "\nFound #{arr.len} such concatenated primes."</lang>
- Output:
Concatenated primes from primes p,q <= 100:
23 37 53 73 113 137 173 193 197 211
223 229 233 241 271 283 293 311 313 317
331 337 347 353 359 367 373 379 383 389
397 433 523 541 547 571 593 613 617 673
677 719 733 743 761 773 797 977 1117 1123
1129 1153 1171 1319 1361 1367 1373 1723 1741 1747
1753 1759 1783 1789 1913 1931 1973 1979 1997 2311
2341 2347 2371 2383 2389 2917 2953 2971 3119 3137
3167 3719 3761 3767 3779 3797 4111 4129 4153 4159
4337 4373 4397 4723 4729 4759 4783 4789 5323 5347
5923 5953 6113 6131 6143 6173 6197 6719 6737 6761
6779 7129 7159 7331 7919 7937 8311 8317 8329 8353
8389 8923 8929 8941 8971 9719 9743 9767
Found 128 such concatenated primes.
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst
var limit = 99 var primes = Int.primeSieve(limit) var results = [] for (p in primes) {
for (q in primes) {
var pq = (q < 10) ? p*10 + q : p*100 + q
if (Int.isPrime(pq)) results.add(pq)
}
} results = Lst.distinct(results) results.sort() System.print("Two primes under 100 concatenated together to form another prime:") for (chunk in Lst.chunks(results, 10)) Fmt.print("$,6d", chunk) System.print("\nFound %(results.count) such concatenated primes.")</lang>
- Output:
Two primes under 100 concatenated together to form another prime:
23 37 53 73 113 137 173 193 197 211
223 229 233 241 271 283 293 311 313 317
331 337 347 353 359 367 373 379 383 389
397 433 523 541 547 571 593 613 617 673
677 719 733 743 761 773 797 977 1,117 1,123
1,129 1,153 1,171 1,319 1,361 1,367 1,373 1,723 1,741 1,747
1,753 1,759 1,783 1,789 1,913 1,931 1,973 1,979 1,997 2,311
2,341 2,347 2,371 2,383 2,389 2,917 2,953 2,971 3,119 3,137
3,167 3,719 3,761 3,767 3,779 3,797 4,111 4,129 4,153 4,159
4,337 4,373 4,397 4,723 4,729 4,759 4,783 4,789 5,323 5,347
5,923 5,953 6,113 6,131 6,143 6,173 6,197 6,719 6,737 6,761
6,779 7,129 7,159 7,331 7,919 7,937 8,311 8,317 8,329 8,353
8,389 8,923 8,929 8,941 8,971 9,719 9,743 9,767
Found 128 such concatenated primes.
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
char Set(9999+1); int P1, P2, P, Count; [for P:= 0 to 9999 do Set(P):= false; for P1:= 0 to 99 do
if IsPrime(P1) then
for P2:= 0 to 99 do
if IsPrime(P2) then
[if P2 >= 10 then
P:= P1*100 + P2
else P:= P1*10 + P2;
if IsPrime(P) then Set(P):= true;
];
Count:= 0; for P:= 0 to 9999 do
if Set(P) then
[IntOut(0, P);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
CrLf(0); IntOut(0, Count); Text(0, " such concatenated primes found. "); ]</lang>
- Output:
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 128 such concatenated primes found.