Concatenate two primes is also prime: Difference between revisions
(→{{header|Ruby}}: Add Ruby) |
m (→{{header|Wren}}: Minor tidy) |
||
(24 intermediate revisions by 17 users not shown) | |||
Line 4: | Line 4: | ||
Find and show here when the concatenation of two primes ('''p<sub>1</sub>''', '''p<sub>2</sub>''') shown in base ten is also prime, where '''p<sub>1</sub>, p<sub>2</sub> < 100'''. |
Find and show here when the concatenation of two primes ('''p<sub>1</sub>''', '''p<sub>2</sub>''') shown in base ten is also prime, where '''p<sub>1</sub>, p<sub>2</sub> < 100'''. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<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 |
|||
V primes = (2..99).filter(n -> is_prime(n)) |
|||
Set[Int] concatPrimes |
|||
L(p1) primes |
|||
L(p2) primes |
|||
V n = p2 + p1 * (I p2 < 10 {10} E 100) |
|||
I is_prime(n) |
|||
concatPrimes.add(n) |
|||
print(‘Found ’concatPrimes.len‘ primes which are a concatenation of two primes below 100:’) |
|||
L(n) sorted(Array(concatPrimes)) |
|||
print(‘#4’.format(n), end' I (L.index + 1) % 16 == 0 {"\n"} E ‘ ’)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
{{libheader|Action! Tool Kit}} |
|||
{{libheader|Action! Sieve of Eratosthenes}} |
|||
<syntaxhighlight lang="action!">INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit |
|||
INCLUDE "H6:SIEVE.ACT" |
|||
PROC Main() |
|||
DEFINE MAX="9999" |
|||
BYTE ARRAY primes(MAX+1) |
|||
BYTE i,j |
|||
INT ij,count |
|||
INT ARRAY res(130) |
|||
Put(125) PutE() ;clear the screen |
|||
Sieve(primes,MAX+1) |
|||
count=0 |
|||
FOR i=2 TO 99 |
|||
DO |
|||
IF primes(i) THEN |
|||
FOR j=2 TO 99 |
|||
DO |
|||
IF primes(j) THEN |
|||
ij=i |
|||
IF j<10 THEN |
|||
ij==*10 |
|||
ELSE |
|||
ij==*100 |
|||
FI |
|||
ij==+j |
|||
IF primes(ij) THEN |
|||
res(count)=ij |
|||
count==+1 |
|||
FI |
|||
FI |
|||
OD |
|||
FI |
|||
OD |
|||
SortI(res,count,0) |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
PrintI(res(i)) Put(32) |
|||
OD |
|||
PrintF("%E%EThere are %I primes",count) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Concatenate_two_primes_is_also_prime.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 313 |
|||
317 317 331 337 347 353 359 367 373 373 379 383 389 397 433 523 541 547 571 |
|||
593 613 617 673 677 719 733 743 761 773 797 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 |
|||
There are 132 primes |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight lang="ada">with Ada.Text_Io; |
|||
with Ada.Integer_Text_Io; |
|||
with Ada.Strings.Fixed; |
|||
procedure Concat_Is_Prime is |
|||
Columns : constant := 10; |
|||
subtype Full_Range is Integer range 2 .. 9_999; |
|||
subtype Low_Range is Full_Range range Full_Range'First .. 99; |
|||
function Concat (Left, Right : Low_Range) return Full_Range is |
|||
use Ada.Strings; |
|||
begin |
|||
return Full_Range'Value (Fixed.Trim (Left'Image, Both) & |
|||
Fixed.Trim (Right'Image, Both)); |
|||
end Concat; |
|||
use Ada.Text_Io, Ada.Integer_Text_Io; |
|||
Is_Prime : array (Full_Range) of Boolean := (others => True); |
|||
Is_Concat_Prime : array (Full_Range) of Boolean := (others => False); |
|||
Count : Natural := 0; |
|||
begin |
|||
for A in Full_Range loop |
|||
if Is_Prime (A) then |
|||
for B in 2 .. Integer'Last loop |
|||
exit when A * B not in Full_Range; |
|||
Is_Prime (A * B) := False; |
|||
end loop; |
|||
end if; |
|||
end loop; |
|||
for P1 in Low_Range loop |
|||
for P2 in Low_Range loop |
|||
if |
|||
Is_Prime (P1) and Is_Prime (P2) and Is_Prime (Concat (P1, P2)) |
|||
then |
|||
Is_Concat_Prime (Concat (P1, P2)) := True; |
|||
end if; |
|||
end loop; |
|||
end loop; |
|||
for A in Is_Concat_Prime'Range loop |
|||
if Is_Concat_Prime (A) then |
|||
Put (A, Width => 6); |
|||
Count := Count + 1; |
|||
if Count mod Columns = 0 then |
|||
New_Line; |
|||
end if; |
|||
end if; |
|||
end loop; |
|||
New_Line; |
|||
Put ("There are "); |
|||
Put (Natural'Image (Count)); |
|||
Put (" concat primes."); |
|||
New_Line; |
|||
end Concat_Is_Prime;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
There are 128 concat primes. |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{libheader|ALGOL 68-primes}} |
|||
<lang algol68>BEGIN # find primes whose decimal representation is the concatenation of 2 primes # |
|||
<syntaxhighlight 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 low prime = 99; # for the task, only need component primes up to 99 # |
||
INT max prime = max low prime * max low prime; |
INT max prime = max low prime * max low prime; |
||
# sieve the primes to max prime # |
# sieve the primes to max prime # |
||
PR read "primes.incl.a68" PR |
|||
[ 1 : max prime ]BOOL prime; |
|||
[]BOOL prime = PRIMESIEVE max prime; |
|||
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 # |
# construct a list of the primes up to the maximum low prime to consider # |
||
[ |
[]INT low prime = EXTRACTPRIMESUPTO max low prime FROMPRIMESIEVE 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 # |
# 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; |
[ 1 : max prime ]BOOL concat prime; FOR i TO UPB concat prime DO concat prime[ i ] := FALSE OD; |
||
Line 42: | Line 214: | ||
OD; |
OD; |
||
print( ( newline, newline, "Found ", whole( c count, 0 ), " concat primes", newline ) ) |
print( ( newline, newline, "Found ", whole( c count, 0 ), " concat primes", newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 64: | Line 236: | ||
=={{header|ALGOL W}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="algolw">begin % find primes whose decimal representation is the concatenation of 2 primes % |
||
integer MAX_PRIME; |
integer MAX_PRIME; |
||
MAX_PRIME := 99 * 99; |
MAX_PRIME := 99 * 99; |
||
Line 102: | Line 274: | ||
write();write( i_w := 1, s_w := 0, "Found ", cCount, " concat primes" ) |
write();write( i_w := 1, s_w := 0, "Found ", cCount, " concat primes" ) |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 121: | Line 293: | ||
Found 128 concat primes |
Found 128 concat primes |
||
</pre> |
</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">primesBelow100: select 1..100 => prime? |
|||
allPossibleConcats: permutate.repeat.by:2 primesBelow100 |
|||
concatPrimes: allPossibleConcats | map 'x -> to :integer (to :string x\[0]) ++ (to :string x\[1]) |
|||
| select => prime? |
|||
| sort |
|||
| unique |
|||
print ["Found" size concatPrimes "concatenations of primes below 100:"] |
|||
loop split.every: 16 concatPrimes 'x -> |
|||
print map x 's -> pad to :string s 4 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Found 128 concatenations of 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</pre> |
|||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f CONCATENATE_TWO_PRIMES_IS_ALSO_PRIME.AWK |
# syntax: GAWK -f CONCATENATE_TWO_PRIMES_IS_ALSO_PRIME.AWK |
||
# |
# |
||
Line 161: | Line 359: | ||
return(1) |
return(1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 179: | Line 377: | ||
Concatenate two primes is also prime 1-99: 128 |
Concatenate two primes is also prime 1-99: 128 |
||
</pre> |
</pre> |
||
=={{header|BASIC}}== |
|||
==={{header|BASIC256}}=== |
|||
<syntaxhighlight lang="basic256">c = 0 |
|||
for p1 = 2 to 99 |
|||
if not isPrime(p1) then continue for |
|||
for p2 = 2 to 99 |
|||
if not isPrime(p2) then continue for |
|||
cat = rjust(string(p1),2) + rjust(string(p2),2) |
|||
if isPrime(cat) then |
|||
c += 1 |
|||
print p1; "|"; p2; " "; |
|||
if c mod 10 = 0 then print |
|||
end if |
|||
next p2 |
|||
next p1 |
|||
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</syntaxhighlight> |
|||
==={{header|FreeBASIC}}=== |
|||
This solution focuses more on the primes p1, p2 than on the concatenated prime. Thus, there can be multiple solutions. For example, 373 can be formed from 37 and 3 or from 3 and 73 and will be listed twice. |
|||
<syntaxhighlight lang="freebasic">#include "isprime.bas" |
|||
dim as integer p1, p2, cat, c = 0 |
|||
for p1 = 2 to 99 |
|||
if not isprime(p1) then continue for |
|||
for p2 = 2 to 99 |
|||
if not isprime(p2) then continue for |
|||
cat = val( str(p1) + str(p2) ) ' =^..^= |
|||
if isprime(cat) then |
|||
c+=1 |
|||
print using "##|## ";p1;p2; |
|||
if c mod 10 = 0 then print |
|||
end if |
|||
next p2 |
|||
next p1 |
|||
</syntaxhighlight> |
|||
{{out}}<pre> |
|||
2| 3 2|11 2|23 2|29 2|41 2|71 2|83 3| 7 3|11 3|13 |
|||
3|17 3|31 3|37 3|47 3|53 3|59 3|67 3|73 3|79 3|83 |
|||
3|89 3|97 5| 3 5|23 5|41 5|47 5|71 7| 3 7|19 7|43 |
|||
7|61 7|73 7|97 11| 3 11|17 11|23 11|29 11|53 11|71 13| 7 |
|||
13|19 13|61 13|67 13|73 17| 3 17|23 17|41 17|47 17|53 17|59 |
|||
17|83 17|89 19| 3 19| 7 19|13 19|31 19|73 19|79 19|97 23| 3 |
|||
23|11 23|41 23|47 23|71 23|83 23|89 29| 3 29|17 29|53 29|71 |
|||
31| 3 31| 7 31|19 31|37 31|67 37| 3 37|19 37|61 37|67 37|79 |
|||
37|97 41|11 41|29 41|53 41|59 43| 3 43|37 43|73 43|97 47|23 |
|||
47|29 47|59 47|83 47|89 53|23 53|47 59| 3 59|23 59|53 61| 3 |
|||
61| 7 61|13 61|31 61|43 61|73 61|97 67| 3 67| 7 67|19 67|37 |
|||
67|61 67|79 71|29 71|59 73| 3 73|31 79| 7 79|19 79|37 83|11 |
|||
83|17 83|29 83|53 83|89 89|23 89|29 89|41 89|71 97| 7 97|19 |
|||
97|43 97|67 |
|||
</pre> |
|||
==={{header|Yabasic}}=== |
|||
<syntaxhighlight lang="yabasic">c = 0 |
|||
for p1 = 2 to 99 |
|||
if not isPrime(p1) then continue : fi |
|||
for p2 = 2 to 99 |
|||
if not isPrime(p2) then continue : fi |
|||
cat = val(str$(p1) + str$(p2)) |
|||
if isPrime(cat) then |
|||
c = c + 1 |
|||
a$ = str$(p1,"##") |
|||
b$ = str$(p2,"##") |
|||
print a$, "|", b$, " "; |
|||
if mod(c, 10) = 0 then print : fi |
|||
end if |
|||
next p2 |
|||
next p1 |
|||
print |
|||
end |
|||
sub isPrime(v) |
|||
if v < 2 then return False : fi |
|||
if mod(v, 2) = 0 then return v = 2 : fi |
|||
if mod(v, 3) = 0 then return v = 3 : fi |
|||
d = 5 |
|||
while d * d <= v |
|||
if mod(v, d) = 0 then return False else d = d + 2 : fi |
|||
wend |
|||
return True |
|||
end sub</syntaxhighlight> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdbool.h> |
|||
#include <locale.h> |
|||
bool isPrime(int n) { |
|||
if (n < 2) return false; |
|||
if (n%2 == 0) return n == 2; |
|||
if (n%3 == 0) return n == 3; |
|||
int d = 5; |
|||
while (d*d <= n) { |
|||
if (n%d == 0) return false; |
|||
d += 2; |
|||
if (n%d == 0) return false; |
|||
d += 4; |
|||
} |
|||
return true; |
|||
} |
|||
int compare(const void* a, const void* b) { |
|||
int arg1 = *(const int*)a; |
|||
int arg2 = *(const int*)b; |
|||
if (arg1 < arg2) return -1; |
|||
if (arg1 > arg2) return 1; |
|||
return 0; |
|||
} |
|||
int main() { |
|||
int primes[30] = {2}, results[200]; |
|||
int i, j, p, q, pq, limit = 100, pc = 1, rc = 0; |
|||
for (i = 3; i < limit; i += 2) { |
|||
if (isPrime(i)) primes[pc++] = i; |
|||
} |
|||
for (i = 0; i < pc; ++i) { |
|||
p = primes[i]; |
|||
for (j = 0; j < pc; ++j) { |
|||
q = primes[j]; |
|||
pq = (q < 10) ? p * 10 + q : p * 100 + q; |
|||
if (isPrime(pq)) results[rc++] = pq; |
|||
} |
|||
} |
|||
qsort(results, rc, sizeof(int), compare); |
|||
setlocale(LC_NUMERIC, ""); |
|||
printf("Two primes under 100 concatenated together to form another prime:\n"); |
|||
for (i = 0, j = 0; i < rc; ++i) { |
|||
if (i > 0 && results[i] == results[i-1]) continue; |
|||
printf("%'6d ", results[i]); |
|||
if (++j % 10 == 0) printf("\n"); |
|||
} |
|||
printf("\n\nFound %d such concatenated primes.\n", j); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function Compare(P1,P2: pointer): integer; |
|||
{Compare for quick sort} |
|||
begin |
|||
Result:=Integer(P1)-Integer(P2); |
|||
end; |
|||
procedure ConcatonatePrimes(Memo: TMemo); |
|||
{Show concatonated pairs of primes that are also prime} |
|||
var List: TList; |
|||
var I,P1,P2,ConCat: integer; |
|||
var Sieve: TPrimeSieve; |
|||
const Max =100; |
|||
var S: string; |
|||
function ConcatNums(I1,I2: integer): integer; |
|||
begin |
|||
Result:=StrToInt(IntToStr(I1)+IntToStr(I2)); |
|||
end; |
|||
begin |
|||
{Create sieve to for fast prime generation} |
|||
Sieve:=TPrimeSieve.Create; |
|||
try |
|||
List:=TList.Create; |
|||
try |
|||
{Sieve first 1,000 primes} |
|||
Sieve.Intialize(1000); |
|||
{Generate all combinations of primes} |
|||
{ P1 and P2, from 2 to 100} |
|||
P1:=2; |
|||
while P1<Max do |
|||
begin |
|||
P2:=2; |
|||
while P2<Max do |
|||
begin |
|||
{Concatonates the two primes} |
|||
ConCat:=ConcatNums(P1,P2); |
|||
{Test if it is prime and only store unique primes} |
|||
if IsPrime(ConCat) then |
|||
if List.IndexOf(Pointer(ConCat))<0 then |
|||
List.Add(Pointer(ConCat)); |
|||
P2:=Sieve.NextPrime(P2); |
|||
end; |
|||
P1:=Sieve.NextPrime(P1); |
|||
end; |
|||
{Sort list in numerical order} |
|||
List.Sort(Compare); |
|||
{Display the result} |
|||
Memo.Lines.Add('Concatonated Primes Found: '+IntToStr(List.Count)); |
|||
for I:=0 to List.Count-1 do |
|||
begin |
|||
S:=S+Format('%5d',[integer(List[I])]); |
|||
if (I mod 10)=9 then S:=S+CRLF; |
|||
end; |
|||
Memo.Lines.Add(S); |
|||
finally List.Free; end; |
|||
finally Sieve.Free; end; |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Concatonated Primes Found: 128 |
|||
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 |
|||
Elapsed Time: 3.990 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
proc sort . d[] . |
|||
for i = 1 to len d[] - 1 |
|||
for j = i + 1 to len d[] |
|||
if d[j] < d[i] |
|||
swap d[j] d[i] |
|||
. |
|||
. |
|||
. |
|||
. |
|||
func isprim num . |
|||
i = 2 |
|||
while i <= sqrt num |
|||
if num mod i = 0 |
|||
return 0 |
|||
. |
|||
i += 1 |
|||
. |
|||
return 1 |
|||
. |
|||
for i = 2 to 99 |
|||
if isprim i = 1 |
|||
prims[] &= i |
|||
. |
|||
. |
|||
for p1 in prims[] |
|||
for p2 in prims[] |
|||
h$ = p1 & p2 |
|||
h = number h$ |
|||
if isprim h = 1 |
|||
r[] &= h |
|||
. |
|||
. |
|||
. |
|||
sort r[] |
|||
print r[] |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-06-02}} |
{{works with|Factor|0.99 2021-06-02}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting grouping io kernel math.parser math.primes |
||
present prettyprint sequences sets sorting ; |
present prettyprint sequences sets sorting ; |
||
Line 188: | Line 683: | ||
99 primes-upto [ present ] map dup [ append dec> ] cartesian-map |
99 primes-upto [ present ] map dup [ append dec> ] cartesian-map |
||
concat [ prime? ] filter members natural-sort [ length ] keep |
concat [ prime? ] filter members natural-sort [ length ] keep |
||
8 group simple-table. "\nFound %d concatenated primes.\n" printf</ |
8 group simple-table. "\nFound %d concatenated primes.\n" printf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 215: | Line 710: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 255: | Line 750: | ||
} |
} |
||
fmt.Println("\n\nFound", len(results), "such concatenated primes.") |
fmt.Println("\n\nFound", len(results), "such concatenated primes.") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 276: | Line 771: | ||
Found 128 such concatenated primes. |
Found 128 such concatenated primes. |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">import Control.Applicative |
|||
import Data.List ( sort ) |
|||
import Data.List.Split ( chunksOf ) |
|||
isPrime :: Int -> Bool |
|||
isPrime n |
|||
|n == 2 = True |
|||
|n == 1 = False |
|||
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root] |
|||
where |
|||
root :: Int |
|||
root = floor $ sqrt $ fromIntegral n |
|||
solution :: [Int] |
|||
solution = sort $ filter isPrime $ map read ( (++) <$> numberlist <*> numberlist ) |
|||
where |
|||
numberlist :: [String] |
|||
numberlist = map show $ filter isPrime [1 .. 99] |
|||
main :: IO ( ) |
|||
main = do |
|||
mapM_ print $ chunksOf 15 solution</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[23,37,53,73,113,137,173,193,197,211,223,229,233,241,271] |
|||
[283,293,311,313,313,317,317,331,337,347,353,359,367,373,373] |
|||
[379,383,389,397,433,523,541,547,571,593,613,617,673,677,719] |
|||
[733,743,761,773,797,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] |
|||
</pre> |
|||
=={{header|J}}== |
|||
<syntaxhighlight lang="j"> concat=. (] + (* 10 ^ #@":))"1 0 |
|||
_12 ]\ /:~ (#~ 1&p:) , concat~ i.&.(p:inv) 100 |
|||
23 37 53 73 113 137 173 193 197 211 223 229 |
|||
233 241 271 283 293 311 313 313 317 317 331 337 |
|||
347 353 359 367 373 373 379 383 389 397 433 523 |
|||
541 547 571 593 613 617 673 677 719 733 743 761 |
|||
773 797 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</syntaxhighlight> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 282: | Line 829: | ||
'''Preliminaries''' |
'''Preliminaries''' |
||
< |
<syntaxhighlight lang="jq">def is_prime: |
||
. as $n |
. as $n |
||
| if ($n < 2) then false |
| if ($n < 2) then false |
||
Line 311: | Line 858: | ||
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"># Emit [p1,p2] where p1 < p2 < . and the concatenation is prime |
||
def concatenative_primes: |
def concatenative_primes: |
||
primes |
primes |
||
Line 322: | Line 869: | ||
[100 | concatenative_primes | join("||")] |
[100 | concatenative_primes | join("||")] |
||
| (nwise(10) | map(lpad(6)) | join(" "))</ |
| (nwise(10) | map(lpad(6)) | join(" "))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 340: | Line 887: | ||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
function catprimes() |
function catprimes() |
||
Line 353: | Line 900: | ||
foreach(p -> print(lpad(last(p), 5), first(p) % 16 == 0 ? "\n" : ""), |
foreach(p -> print(lpad(last(p), 5), first(p) % 16 == 0 ? "\n" : ""), |
||
catprimes() |> enumerate) |
catprimes() |> enumerate) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 |
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 |
||
Line 363: | Line 910: | ||
4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 |
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 |
7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 |
||
</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">Select[Catenate /* FromDigits /@ Map[IntegerDigits, Tuples[Prime[Range[PrimePi[100]]], 2], {2}], PrimeQ] // Union</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{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}</pre> |
|||
=={{header|Lua}}== |
|||
Based on the Algol W sample. |
|||
<syntaxhighlight lang="lua"> |
|||
do -- find primes whose decimal representation is the concatenation of 2 primes < 100 |
|||
local MAX_PRIME = 99 * 99 |
|||
-- returns true if n is prime, false otherwise, uses trial division |
|||
local function isPrime ( n ) |
|||
if n < 3 then return n == 2 |
|||
elseif n % 3 == 0 then return n == 3 |
|||
elseif n % 2 == 0 then return false |
|||
else |
|||
local prime = true |
|||
local f, f2, toNext = 5, 25, 24 |
|||
while f2 <= n and prime do |
|||
prime = n % f ~= 0 |
|||
f = f + 2 |
|||
f2 = toNext |
|||
toNext = toNext + 8 |
|||
end |
|||
return prime |
|||
end |
|||
end |
|||
local concatPrime = {} |
|||
-- tables of small primes, sp2 will be the final digits so does not include 2 or 5 |
|||
local sp1 = { 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 |
|||
} |
|||
local sp2 = { 3, 7, 11, 13, 17, 19, 23, 29, 31, 37 |
|||
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 |
|||
} |
|||
-- find the concatenated primes |
|||
for i = 1, MAX_PRIME do concatPrime[ i ] = false end |
|||
for _, p1 in pairs( sp1 ) do |
|||
for _, p2 in pairs( sp2 ) do |
|||
local pc = ( p1 * ( p2 < 10 and 10 or 100 ) ) + p2 |
|||
concatPrime[ pc ] = isPrime( pc ) |
|||
end |
|||
end |
|||
-- print the concatenated primes |
|||
local cCount = 0 |
|||
for i = 1, MAX_PRIME do |
|||
if concatPrime[ i ] then |
|||
io.write( string.format( "%5d", i ) ) |
|||
cCount = cCount + 1 |
|||
if cCount % 10 == 0 then io.write( "\n" ) end |
|||
end |
|||
end |
|||
io.write( "\n\nFound ", cCount, " concat primes" ) |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import strutils, sugar |
||
func isPrime(n: Positive): bool = |
func isPrime(n: Positive): bool = |
||
Line 393: | Line 1,014: | ||
for n in concatPrimes: |
for n in concatPrimes: |
||
stdout.write ($n).align(4), if i mod 16 == 0: '\n' else: ' ' |
stdout.write ($n).align(4), if i mod 16 == 0: '\n' else: ' ' |
||
inc i</ |
inc i</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 407: | Line 1,028: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Concatenate_two_primes_is_also_prime |
use strict; # https://rosettacode.org/wiki/Concatenate_two_primes_is_also_prime |
||
Line 417: | Line 1,038: | ||
my @valid = uniq sort { $a <=> $b } grep is_prime($_), |
my @valid = uniq sort { $a <=> $b } grep is_prime($_), |
||
map { my $prefix = $_; map "$prefix$_", @primes } @primes; |
map { my $prefix = $_; map "$prefix$_", @primes } @primes; |
||
print @valid . " primes found\n\n@valid\n" =~ s/.{79}\K /\n/gr;</ |
print @valid . " primes found\n\n@valid\n" =~ s/.{79}\K /\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 433: | Line 1,054: | ||
=={{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;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">),</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">),</span> |
||
Line 447: | Line 1,068: | ||
<span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (see note)</span> |
<span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (see note)</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;">"Found %d such primes: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</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;">"Found %d such primes: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
<small>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.<br> |
<small>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.<br> |
||
While the (human-readable) error message (without it) is deep within sort(), the call stack makes it clear where that call should best go.</small> |
While the (human-readable) error message (without it) is deep within sort(), the call stack makes it clear where that call should best go.</small> |
||
Line 453: | Line 1,074: | ||
<pre> |
<pre> |
||
Found 128 such primes: {23,37,53,73,113,"...",8941,8971,9719,9743,9767} |
Found 128 such primes: {23,37,53,73,113,"...",8941,8971,9719,9743,9767} |
||
</pre> |
|||
=={{header|PL/M}}== |
|||
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator) |
|||
<syntaxhighlight lang="plm"> |
|||
100H: /* FIND SOME PAIRS OF PRIMES BETWEEN 1 AND 99 SUCH THAT IF THEIR */ |
|||
/* DIGITS ARE CONCATENATED, THE RESULT IS ALSO A PRIME */ |
|||
/* CP/M BDOS SYSTEM CALL AND I/O ROUTINES */ |
|||
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END; |
|||
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END; |
|||
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END; |
|||
PR$NL: PROCEDURE; CALL PR$STRING( .( 0DH, 0AH, '$' ) ); END; |
|||
PR$NUMBER: PROCEDURE( N ); |
|||
DECLARE N ADDRESS; |
|||
DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE; |
|||
V = N; |
|||
W = LAST( N$STR ); |
|||
N$STR( W ) = '$'; |
|||
N$STR( W := W - 1 ) = '0' + ( V MOD 10 ); |
|||
DO WHILE( ( V := V / 10 ) > 0 ); |
|||
N$STR( W := W - 1 ) = '0' + ( V MOD 10 ); |
|||
END; |
|||
CALL PR$STRING( .N$STR( W ) ); |
|||
END PR$NUMBER; |
|||
/* TASK */ |
|||
DECLARE FALSE LITERALLY '0'; |
|||
DECLARE TRUE LITERALLY '0FFH'; |
|||
DECLARE CONCAT$PRIME LITERALLY '0FH'; |
|||
DECLARE MAX$LOW$PRIME LITERALLY '99'; |
|||
DECLARE PRIME ( 10$000 )BYTE; /* PRIME SIEVE. A BIT LARGER THN NEEDED */ |
|||
/* THE FIRST NYBBLE WILL BE SET TO 0 IF */ |
|||
/* IT IS A CONCATENATED PRIME */ |
|||
/* THE SIZE OF PRIME SHOULD BE AT LEAST MAX$LOW$PRIME SQUARED */ |
|||
/* SIEVE THE PRIMES TO MAX$PRIME */ |
|||
DECLARE ( I, J, COUNT ) ADDRESS; |
|||
PRIME( 1 ) = FALSE; PRIME( 2 ) = TRUE; |
|||
DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END; |
|||
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END; |
|||
DO I = 3 TO MAX$LOW$PRIME + 1; |
|||
IF PRIME( I ) THEN DO; |
|||
DO J = I * I TO LAST( PRIME ) BY I + I; PRIME( J ) = FALSE; END; |
|||
END; |
|||
END; |
|||
/* FIND THE CONCATEDNATED PRIMES */ |
|||
COUNT = 0; |
|||
DO I = 2 TO MAX$LOW$PRIME; |
|||
IF PRIME( I ) THEN DO; |
|||
DO J = 2 TO MAX$LOW$PRIME; |
|||
IF PRIME( J ) THEN DO; |
|||
DECLARE CP ADDRESS; |
|||
IF J < 10 THEN CP = I * 10; |
|||
ELSE CP = I * 100; |
|||
CP = CP + J; |
|||
IF PRIME( I ) AND PRIME( J ) AND PRIME( CP ) THEN DO; |
|||
/* CP IS A CONCATENATED PRIME - FLAG PRIME( CP ) AS SUCH */ |
|||
PRIME( CP ) = CONCAT$PRIME; |
|||
END; |
|||
END; |
|||
END; |
|||
END; |
|||
END; |
|||
/* SHOW THE CONCATENATED PRIMES */ |
|||
/* SINGLE DIGIT NUMBERS CAN'T BE CONCATENATED PRIMES, START AT 10 */ |
|||
DO I = 3 TO LAST( PRIME ) BY 2; |
|||
IF PRIME( I ) = CONCAT$PRIME THEN DO; |
|||
/* HAVE A CONCATENATED PRIME */ |
|||
CALL PR$CHAR( ' ' ); |
|||
IF I < 1000 THEN DO; |
|||
CALL PR$CHAR( ' ' ); |
|||
IF I < 100 THEN CALL PR$CHAR( ' ' ); |
|||
END; |
|||
CALL PR$NUMBER( I ); |
|||
IF ( COUNT := COUNT + 1 ) MOD 10 = 0 THEN CALL PR$NL; |
|||
END; |
|||
END; |
|||
EOF |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="python">from itertools import takewhile |
|||
def is_prime(x): |
|||
return x > 1 and all(x % d for d in takewhile(lambda n: n * n <= x, primes)) |
|||
def init_primes(n): |
|||
global primes |
|||
primes = [2] |
|||
for x in range(3, n + 1, 2): |
|||
if is_prime(x): primes.append(x) |
|||
def concat(x, y): |
|||
return 10 ** len(str(y)) * x + y |
|||
init_primes(99) |
|||
print(*sorted(n for x in primes for y in primes if is_prime(n := concat(x, y))))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 313 317 317 331 337 347 353 359 367 373 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 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</pre> |
|||
=={{header|Quackery}}== |
|||
<code>isprime</code> is defined at [[Primality by trial division#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ [] swap |
|||
[ base share /mod |
|||
rot join swap |
|||
dup 0 = until ] |
|||
drop ] is digits ( n --> [ ) |
|||
[ 0 swap witheach |
|||
[ swap 10 * + ] ] is digits->n ( [ --> n ) |
|||
[ behead dup dip nested rot |
|||
witheach |
|||
[ tuck != if |
|||
[ dup dip |
|||
[ nested join ] ] ] |
|||
drop ] is -duplicates ( [ --> [ ) |
|||
[] dup temp put |
|||
100 times |
|||
[ i^ isprime if |
|||
[ i^ digits |
|||
nested join ] ] |
|||
dup witheach |
|||
[ over witheach |
|||
[ over join |
|||
digits->n |
|||
dup isprime iff |
|||
[ temp take |
|||
join |
|||
temp put ] |
|||
else drop ] |
|||
drop ] |
|||
drop |
|||
temp take |
|||
sort -duplicates |
|||
[ dup [] != while |
|||
10 split swap |
|||
witheach |
|||
[ dup 1000 < if sp |
|||
dup 100 < if sp |
|||
echo sp ] |
|||
cr |
|||
again ] |
|||
drop</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 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 |
|||
</pre> |
</pre> |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Inefficient, but for a limit of 100, who cares? |
Inefficient, but for a limit of 100, who cares? |
||
<lang |
<syntaxhighlight lang="raku" line>my @p = ^1e2 .grep: *.is-prime; |
||
say display ( @p X~ @p ).grep( *.is-prime ).unique.sort( +* ); |
say display ( @p X~ @p ).grep( *.is-prime ).unique.sort( +* ); |
||
Line 464: | Line 1,266: | ||
cache $list; |
cache $list; |
||
$title ~ $list.batch($cols)».fmt($fmt).join: "\n" |
$title ~ $list.batch($cols)».fmt($fmt).join: "\n" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>128 matching: |
<pre>128 matching: |
||
Line 482: | Line 1,284: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm finds base ten neighbor primes P1 & P2, when concatenated, is also a prime.*/ |
||
parse arg hip cols . /*obtain optional arguments from the CL*/ |
parse arg hip cols . /*obtain optional arguments from the CL*/ |
||
if hip=='' | hip=="," then hip= 100 /*Not specified? Then use the default.*/ |
if hip=='' | hip=="," then hip= 100 /*Not specified? Then use the default.*/ |
||
if cols=='' | cols=="," then cols= 10 /* " " " " " " */ |
if cols=='' | cols=="," then cols= 10 /* " " " " " " */ |
||
call genP /*build array of semaphores for primes.*/ |
call genP /*build array of semaphores for primes.*/ |
||
title= ' concatenation of two primes (P1, P2) in base ten that results in |
title= ' concatenation of two neighbor 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. */ |
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 ' index │'center(title, 1 + cols*(w+1) ) |
||
Line 495: | Line 1,297: | ||
do j=1 for ## /*search through specified primes. */ |
do j=1 for ## /*search through specified primes. */ |
||
do k=1 for ##; cat2= @.j || @.k /*create a concatenated prime (base 10)*/ |
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. */ |
if !.cat2 then a.cat2= 1 /*flag it as being a "2cat" prime. */ |
||
end /*k*/ /* [↑] forgoes the need for sorting. */ |
end /*k*/ /* [↑] forgoes the need for sorting. */ |
||
end /*j*/ |
end /*j*/ |
||
found= 0; |
found= 0; idx= 1 /*initialize # of primes found; IDX. */ |
||
$=; do n=1 by 2 for hip**2%2 /*search for odd "cat2" primes. */ |
$=; do n=1 by 2 for hip**2%2 /*search for odd "cat2" primes. */ |
||
if \a.n then iterate /*search through allowable primes. */ |
if \a.n then iterate /*search through allowable primes. */ |
||
Line 513: | Line 1,315: | ||
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') |
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') |
||
say |
say |
||
say 'Found ' |
say 'Found ' commas(found) title |
||
exit 0 /*stick a fork in it, we're all done. */ |
exit 0 /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
Line 522: | Line 1,324: | ||
#= 5; sq.#= @.#**2 /*the square of the highest low prime. */ |
#= 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. */ |
do j=@.#+2 by 2 to hip**2-1 /*find odd primes from here on. */ |
||
parse var j '' -1 _; |
parse var j '' -1 _; if _==5 then iterate /*J ÷ by 5? (right digit).*/ |
||
if j//3==0 then iterate; if j//7==0 then iterate /*" " " 3? J ÷ by 7? */ |
|||
if j// 7==0 then iterate /*" " " 7? */ |
|||
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/ |
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. ___ */ |
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ |
||
Line 530: | Line 1,331: | ||
#= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ |
#= #+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. */ |
if j<hip then ##= # /*find a shortcut for the 1st DO loop. */ |
||
end /*j*/; return</ |
end /*j*/; return</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
index │ |
index │ concatenation of two neighbor 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 |
1 │ 23 37 53 73 113 137 173 193 197 211 |
||
Line 550: | Line 1,351: | ||
───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── |
───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── |
||
Found 128 concatenation of two primes (P1, P2) in base ten that results in a prime, |
Found 128 concatenation of two neighbor primes (P1, P2) in base ten that results in a prime, where P1 & P2 are < 100 |
||
</pre> |
</pre> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
see "working..." + nl |
||
Line 597: | Line 1,398: | ||
see nl + "Found " + row + " prime numbers" + nl |
see nl + "Found " + row + " prime numbers" + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 617: | Line 1,418: | ||
Found 128 prime numbers |
Found 128 prime numbers |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|HP|49}} |
|||
≪ { } 2 |
|||
'''DO''' |
|||
3 |
|||
'''DO''' |
|||
OVER →STR OVER + STR→ |
|||
'''IF''' DUP ISPRIME? '''THEN''' |
|||
4 ROLL SWAP |
|||
'''IF''' DUP2 POS NOT '''THEN''' + '''ELSE''' DROP '''END''' |
|||
UNROT |
|||
'''ELSE''' DROP '''END''' |
|||
NEXTPRIME |
|||
'''UNTIL''' DUP 100 > '''END''' |
|||
DROP NEXTPRIME |
|||
'''UNTIL''' DUP 100 > '''END''' |
|||
SORT |
|||
≫ '<span style="color:blue">P1P2</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
1: { 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 } |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require "prime" |
||
concats = Prime.each(100).to_a.repeated_permutation(2).filter_map do |pair| |
concats = Prime.each(100).to_a.repeated_permutation(2).filter_map do |pair| |
||
Line 628: | Line 1,453: | ||
concats = concats.sort.uniq |
concats = concats.sort.uniq |
||
concats.each_slice(10){|slice|puts slice.map{|el| el.to_s.ljust(6)}.join }</ |
concats.each_slice(10){|slice|puts slice.map{|el| el.to_s.ljust(6)}.join }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>23 37 53 73 113 137 173 193 197 211 |
<pre>23 37 53 73 113 137 173 193 197 211 |
||
Line 644: | Line 1,469: | ||
8389 8923 8929 8941 8971 9719 9743 9767 |
8389 8923 8929 8941 8971 9719 9743 9767 |
||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var upto = 100 |
||
var arr = upto.primes |
var arr = upto.primes |
||
var base = 10 |
var base = 10 |
||
Line 660: | Line 1,486: | ||
}) |
}) |
||
say "\nFound #{arr.len} such concatenated primes."</ |
say "\nFound #{arr.len} such concatenated primes."</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 685: | Line 1,511: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int |
||
import "/fmt" for Fmt |
import "./fmt" for Fmt |
||
import "/seq" for Lst |
import "./seq" for Lst |
||
var limit = 99 |
var limit = 99 |
||
Line 701: | Line 1,527: | ||
results.sort() |
results.sort() |
||
System.print("Two primes under 100 concatenated together to form another prime:") |
System.print("Two primes under 100 concatenated together to form another prime:") |
||
Fmt.tprint("$,6d", results, 10) |
|||
for (chunk in Lst.chunks(results, 10)) Fmt.print("$,6d", chunk) |
|||
System.print("\nFound %(results.count) such concatenated primes.")</ |
System.print("\nFound %(results.count) such concatenated primes.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 725: | Line 1,551: | ||
=={{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 756: | Line 1,582: | ||
Text(0, " such concatenated primes found. |
Text(0, " such concatenated primes found. |
||
"); |
"); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 16:28, 20 November 2023
- Task
Find and show here when the concatenation of two primes (p1, p2) shown in base ten is also prime, where p1, p2 < 100.
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
V primes = (2..99).filter(n -> is_prime(n))
Set[Int] concatPrimes
L(p1) primes
L(p2) primes
V n = p2 + p1 * (I p2 < 10 {10} E 100)
I is_prime(n)
concatPrimes.add(n)
print(‘Found ’concatPrimes.len‘ primes which are a concatenation of two primes below 100:’)
L(n) sorted(Array(concatPrimes))
print(‘#4’.format(n), end' I (L.index + 1) % 16 == 0 {"\n"} E ‘ ’)
- 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
Action!
INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit
INCLUDE "H6:SIEVE.ACT"
PROC Main()
DEFINE MAX="9999"
BYTE ARRAY primes(MAX+1)
BYTE i,j
INT ij,count
INT ARRAY res(130)
Put(125) PutE() ;clear the screen
Sieve(primes,MAX+1)
count=0
FOR i=2 TO 99
DO
IF primes(i) THEN
FOR j=2 TO 99
DO
IF primes(j) THEN
ij=i
IF j<10 THEN
ij==*10
ELSE
ij==*100
FI
ij==+j
IF primes(ij) THEN
res(count)=ij
count==+1
FI
FI
OD
FI
OD
SortI(res,count,0)
FOR i=0 TO count-1
DO
PrintI(res(i)) Put(32)
OD
PrintF("%E%EThere are %I primes",count)
RETURN
- Output:
Screenshot from Atari 8-bit computer
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 313 317 317 331 337 347 353 359 367 373 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 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 There are 132 primes
Ada
with Ada.Text_Io;
with Ada.Integer_Text_Io;
with Ada.Strings.Fixed;
procedure Concat_Is_Prime is
Columns : constant := 10;
subtype Full_Range is Integer range 2 .. 9_999;
subtype Low_Range is Full_Range range Full_Range'First .. 99;
function Concat (Left, Right : Low_Range) return Full_Range is
use Ada.Strings;
begin
return Full_Range'Value (Fixed.Trim (Left'Image, Both) &
Fixed.Trim (Right'Image, Both));
end Concat;
use Ada.Text_Io, Ada.Integer_Text_Io;
Is_Prime : array (Full_Range) of Boolean := (others => True);
Is_Concat_Prime : array (Full_Range) of Boolean := (others => False);
Count : Natural := 0;
begin
for A in Full_Range loop
if Is_Prime (A) then
for B in 2 .. Integer'Last loop
exit when A * B not in Full_Range;
Is_Prime (A * B) := False;
end loop;
end if;
end loop;
for P1 in Low_Range loop
for P2 in Low_Range loop
if
Is_Prime (P1) and Is_Prime (P2) and Is_Prime (Concat (P1, P2))
then
Is_Concat_Prime (Concat (P1, P2)) := True;
end if;
end loop;
end loop;
for A in Is_Concat_Prime'Range loop
if Is_Concat_Prime (A) then
Put (A, Width => 6);
Count := Count + 1;
if Count mod Columns = 0 then
New_Line;
end if;
end if;
end loop;
New_Line;
Put ("There are ");
Put (Natural'Image (Count));
Put (" concat primes.");
New_Line;
end Concat_Is_Prime;
- 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 There are 128 concat primes.
ALGOL 68
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 #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE max prime;
# construct a list of the primes up to the maximum low prime to consider #
[]INT low prime = EXTRACTPRIMESUPTO max low prime FROMPRIMESIEVE prime;
# 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
- 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.
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.
- 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
Arturo
primesBelow100: select 1..100 => prime?
allPossibleConcats: permutate.repeat.by:2 primesBelow100
concatPrimes: allPossibleConcats | map 'x -> to :integer (to :string x\[0]) ++ (to :string x\[1])
| select => prime?
| sort
| unique
print ["Found" size concatPrimes "concatenations of primes below 100:"]
loop split.every: 16 concatPrimes 'x ->
print map x 's -> pad to :string s 4
- Output:
Found 128 concatenations of 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
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)
}
- 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
BASIC
BASIC256
c = 0
for p1 = 2 to 99
if not isPrime(p1) then continue for
for p2 = 2 to 99
if not isPrime(p2) then continue for
cat = rjust(string(p1),2) + rjust(string(p2),2)
if isPrime(cat) then
c += 1
print p1; "|"; p2; " ";
if c mod 10 = 0 then print
end if
next p2
next p1
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
FreeBASIC
This solution focuses more on the primes p1, p2 than on the concatenated prime. Thus, there can be multiple solutions. For example, 373 can be formed from 37 and 3 or from 3 and 73 and will be listed twice.
#include "isprime.bas"
dim as integer p1, p2, cat, c = 0
for p1 = 2 to 99
if not isprime(p1) then continue for
for p2 = 2 to 99
if not isprime(p2) then continue for
cat = val( str(p1) + str(p2) ) ' =^..^=
if isprime(cat) then
c+=1
print using "##|## ";p1;p2;
if c mod 10 = 0 then print
end if
next p2
next p1
- Output:
2| 3 2|11 2|23 2|29 2|41 2|71 2|83 3| 7 3|11 3|13 3|17 3|31 3|37 3|47 3|53 3|59 3|67 3|73 3|79 3|83 3|89 3|97 5| 3 5|23 5|41 5|47 5|71 7| 3 7|19 7|43 7|61 7|73 7|97 11| 3 11|17 11|23 11|29 11|53 11|71 13| 7 13|19 13|61 13|67 13|73 17| 3 17|23 17|41 17|47 17|53 17|59 17|83 17|89 19| 3 19| 7 19|13 19|31 19|73 19|79 19|97 23| 3 23|11 23|41 23|47 23|71 23|83 23|89 29| 3 29|17 29|53 29|71 31| 3 31| 7 31|19 31|37 31|67 37| 3 37|19 37|61 37|67 37|79 37|97 41|11 41|29 41|53 41|59 43| 3 43|37 43|73 43|97 47|23 47|29 47|59 47|83 47|89 53|23 53|47 59| 3 59|23 59|53 61| 3 61| 7 61|13 61|31 61|43 61|73 61|97 67| 3 67| 7 67|19 67|37 67|61 67|79 71|29 71|59 73| 3 73|31 79| 7 79|19 79|37 83|11 83|17 83|29 83|53 83|89 89|23 89|29 89|41 89|71 97| 7 97|19 97|43 97|67
Yabasic
c = 0
for p1 = 2 to 99
if not isPrime(p1) then continue : fi
for p2 = 2 to 99
if not isPrime(p2) then continue : fi
cat = val(str$(p1) + str$(p2))
if isPrime(cat) then
c = c + 1
a$ = str$(p1,"##")
b$ = str$(p2,"##")
print a$, "|", b$, " ";
if mod(c, 10) = 0 then print : fi
end if
next p2
next p1
print
end
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
int compare(const void* a, const void* b) {
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
int main() {
int primes[30] = {2}, results[200];
int i, j, p, q, pq, limit = 100, pc = 1, rc = 0;
for (i = 3; i < limit; i += 2) {
if (isPrime(i)) primes[pc++] = i;
}
for (i = 0; i < pc; ++i) {
p = primes[i];
for (j = 0; j < pc; ++j) {
q = primes[j];
pq = (q < 10) ? p * 10 + q : p * 100 + q;
if (isPrime(pq)) results[rc++] = pq;
}
}
qsort(results, rc, sizeof(int), compare);
setlocale(LC_NUMERIC, "");
printf("Two primes under 100 concatenated together to form another prime:\n");
for (i = 0, j = 0; i < rc; ++i) {
if (i > 0 && results[i] == results[i-1]) continue;
printf("%'6d ", results[i]);
if (++j % 10 == 0) printf("\n");
}
printf("\n\nFound %d such concatenated primes.\n", j);
return 0;
}
- 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.
Delphi
function Compare(P1,P2: pointer): integer;
{Compare for quick sort}
begin
Result:=Integer(P1)-Integer(P2);
end;
procedure ConcatonatePrimes(Memo: TMemo);
{Show concatonated pairs of primes that are also prime}
var List: TList;
var I,P1,P2,ConCat: integer;
var Sieve: TPrimeSieve;
const Max =100;
var S: string;
function ConcatNums(I1,I2: integer): integer;
begin
Result:=StrToInt(IntToStr(I1)+IntToStr(I2));
end;
begin
{Create sieve to for fast prime generation}
Sieve:=TPrimeSieve.Create;
try
List:=TList.Create;
try
{Sieve first 1,000 primes}
Sieve.Intialize(1000);
{Generate all combinations of primes}
{ P1 and P2, from 2 to 100}
P1:=2;
while P1<Max do
begin
P2:=2;
while P2<Max do
begin
{Concatonates the two primes}
ConCat:=ConcatNums(P1,P2);
{Test if it is prime and only store unique primes}
if IsPrime(ConCat) then
if List.IndexOf(Pointer(ConCat))<0 then
List.Add(Pointer(ConCat));
P2:=Sieve.NextPrime(P2);
end;
P1:=Sieve.NextPrime(P1);
end;
{Sort list in numerical order}
List.Sort(Compare);
{Display the result}
Memo.Lines.Add('Concatonated Primes Found: '+IntToStr(List.Count));
for I:=0 to List.Count-1 do
begin
S:=S+Format('%5d',[integer(List[I])]);
if (I mod 10)=9 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
finally List.Free; end;
finally Sieve.Free; end;
end;
- Output:
Concatonated Primes Found: 128 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 Elapsed Time: 3.990 ms.
EasyLang
proc sort . d[] .
for i = 1 to len d[] - 1
for j = i + 1 to len d[]
if d[j] < d[i]
swap d[j] d[i]
.
.
.
.
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
for i = 2 to 99
if isprim i = 1
prims[] &= i
.
.
for p1 in prims[]
for p2 in prims[]
h$ = p1 & p2
h = number h$
if isprim h = 1
r[] &= h
.
.
.
sort r[]
print r[]
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
- 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
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.")
}
- 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.
Haskell
import Control.Applicative
import Data.List ( sort )
import Data.List.Split ( chunksOf )
isPrime :: Int -> Bool
isPrime n
|n == 2 = True
|n == 1 = False
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root]
where
root :: Int
root = floor $ sqrt $ fromIntegral n
solution :: [Int]
solution = sort $ filter isPrime $ map read ( (++) <$> numberlist <*> numberlist )
where
numberlist :: [String]
numberlist = map show $ filter isPrime [1 .. 99]
main :: IO ( )
main = do
mapM_ print $ chunksOf 15 solution
- Output:
[23,37,53,73,113,137,173,193,197,211,223,229,233,241,271] [283,293,311,313,313,317,317,331,337,347,353,359,367,373,373] [379,383,389,397,433,523,541,547,571,593,613,617,673,677,719] [733,743,761,773,797,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]
J
concat=. (] + (* 10 ^ #@":))"1 0
_12 ]\ /:~ (#~ 1&p:) , concat~ i.&.(p:inv) 100
23 37 53 73 113 137 173 193 197 211 223 229
233 241 271 283 293 311 313 313 317 317 331 337
347 353 359 367 373 373 379 383 389 397 433 523
541 547 571 593 613 617 673 677 719 733 743 761
773 797 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
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;
# 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
# 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(" "))
- 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
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)
- 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
Mathematica/Wolfram Language
Select[Catenate /* FromDigits /@ Map[IntegerDigits, Tuples[Prime[Range[PrimePi[100]]], 2], {2}], PrimeQ] // Union
- 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}
Lua
Based on the Algol W sample.
do -- find primes whose decimal representation is the concatenation of 2 primes < 100
local MAX_PRIME = 99 * 99
-- returns true if n is prime, false otherwise, uses trial division
local function isPrime ( n )
if n < 3 then return n == 2
elseif n % 3 == 0 then return n == 3
elseif n % 2 == 0 then return false
else
local prime = true
local f, f2, toNext = 5, 25, 24
while f2 <= n and prime do
prime = n % f ~= 0
f = f + 2
f2 = toNext
toNext = toNext + 8
end
return prime
end
end
local concatPrime = {}
-- tables of small primes, sp2 will be the final digits so does not include 2 or 5
local sp1 = { 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
}
local sp2 = { 3, 7, 11, 13, 17, 19, 23, 29, 31, 37
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
}
-- find the concatenated primes
for i = 1, MAX_PRIME do concatPrime[ i ] = false end
for _, p1 in pairs( sp1 ) do
for _, p2 in pairs( sp2 ) do
local pc = ( p1 * ( p2 < 10 and 10 or 100 ) ) + p2
concatPrime[ pc ] = isPrime( pc )
end
end
-- print the concatenated primes
local cCount = 0
for i = 1, MAX_PRIME do
if concatPrime[ i ] then
io.write( string.format( "%5d", i ) )
cCount = cCount + 1
if cCount % 10 == 0 then io.write( "\n" ) end
end
end
io.write( "\n\nFound ", cCount, " concat primes" )
end
- 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
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
- 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
#!/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;
- 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}
PL/M
... under CP/M (or an emulator)
100H: /* FIND SOME PAIRS OF PRIMES BETWEEN 1 AND 99 SUCH THAT IF THEIR */
/* DIGITS ARE CONCATENATED, THE RESULT IS ALSO A PRIME */
/* CP/M BDOS SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$STRING( .( 0DH, 0AH, '$' ) ); END;
PR$NUMBER: PROCEDURE( N );
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* TASK */
DECLARE FALSE LITERALLY '0';
DECLARE TRUE LITERALLY '0FFH';
DECLARE CONCAT$PRIME LITERALLY '0FH';
DECLARE MAX$LOW$PRIME LITERALLY '99';
DECLARE PRIME ( 10$000 )BYTE; /* PRIME SIEVE. A BIT LARGER THN NEEDED */
/* THE FIRST NYBBLE WILL BE SET TO 0 IF */
/* IT IS A CONCATENATED PRIME */
/* THE SIZE OF PRIME SHOULD BE AT LEAST MAX$LOW$PRIME SQUARED */
/* SIEVE THE PRIMES TO MAX$PRIME */
DECLARE ( I, J, COUNT ) ADDRESS;
PRIME( 1 ) = FALSE; PRIME( 2 ) = TRUE;
DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END;
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
DO I = 3 TO MAX$LOW$PRIME + 1;
IF PRIME( I ) THEN DO;
DO J = I * I TO LAST( PRIME ) BY I + I; PRIME( J ) = FALSE; END;
END;
END;
/* FIND THE CONCATEDNATED PRIMES */
COUNT = 0;
DO I = 2 TO MAX$LOW$PRIME;
IF PRIME( I ) THEN DO;
DO J = 2 TO MAX$LOW$PRIME;
IF PRIME( J ) THEN DO;
DECLARE CP ADDRESS;
IF J < 10 THEN CP = I * 10;
ELSE CP = I * 100;
CP = CP + J;
IF PRIME( I ) AND PRIME( J ) AND PRIME( CP ) THEN DO;
/* CP IS A CONCATENATED PRIME - FLAG PRIME( CP ) AS SUCH */
PRIME( CP ) = CONCAT$PRIME;
END;
END;
END;
END;
END;
/* SHOW THE CONCATENATED PRIMES */
/* SINGLE DIGIT NUMBERS CAN'T BE CONCATENATED PRIMES, START AT 10 */
DO I = 3 TO LAST( PRIME ) BY 2;
IF PRIME( I ) = CONCAT$PRIME THEN DO;
/* HAVE A CONCATENATED PRIME */
CALL PR$CHAR( ' ' );
IF I < 1000 THEN DO;
CALL PR$CHAR( ' ' );
IF I < 100 THEN CALL PR$CHAR( ' ' );
END;
CALL PR$NUMBER( I );
IF ( COUNT := COUNT + 1 ) MOD 10 = 0 THEN CALL PR$NL;
END;
END;
EOF
- 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
Python
from itertools import takewhile
def is_prime(x):
return x > 1 and all(x % d for d in takewhile(lambda n: n * n <= x, primes))
def init_primes(n):
global primes
primes = [2]
for x in range(3, n + 1, 2):
if is_prime(x): primes.append(x)
def concat(x, y):
return 10 ** len(str(y)) * x + y
init_primes(99)
print(*sorted(n for x in primes for y in primes if is_prime(n := concat(x, y))))
- Output:
23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 313 317 317 331 337 347 353 359 367 373 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 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
Quackery
isprime
is defined at Primality by trial division#Quackery.
[ [] swap
[ base share /mod
rot join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
[ 0 swap witheach
[ swap 10 * + ] ] is digits->n ( [ --> n )
[ behead dup dip nested rot
witheach
[ tuck != if
[ dup dip
[ nested join ] ] ]
drop ] is -duplicates ( [ --> [ )
[] dup temp put
100 times
[ i^ isprime if
[ i^ digits
nested join ] ]
dup witheach
[ over witheach
[ over join
digits->n
dup isprime iff
[ temp take
join
temp put ]
else drop ]
drop ]
drop
temp take
sort -duplicates
[ dup [] != while
10 split swap
witheach
[ dup 1000 < if sp
dup 100 < if sp
echo sp ]
cr
again ]
drop
- 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
Raku
Inefficient, but for a limit of 100, who cares?
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"
}
- 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
/*REXX pgm finds base ten neighbor 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 neighbor 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 ÷ by 5? (right digit).*/
if j//3==0 then iterate; if j//7==0 then iterate /*" " " 3? J ÷ by 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
- output when using the default inputs:
index │ concatenation of two neighbor 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 neighbor primes (P1, P2) in base ten that results in a prime, where P1 & P2 are < 100
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
- 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...
RPL
≪ { } 2
DO
3
DO
OVER →STR OVER + STR→
IF DUP ISPRIME? THEN
4 ROLL SWAP
IF DUP2 POS NOT THEN + ELSE DROP END
UNROT
ELSE DROP END
NEXTPRIME
UNTIL DUP 100 > END
DROP NEXTPRIME
UNTIL DUP 100 > END
SORT
≫ 'P1P2' STO
- Output:
1: { 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 }
Ruby
require "prime"
concats = Prime.each(100).to_a.repeated_permutation(2).filter_map do |pair|
p1p2 = pair.map(&:to_s).join.to_i
p1p2 if p1p2.prime?
end
concats = concats.sort.uniq
concats.each_slice(10){|slice|puts slice.map{|el| el.to_s.ljust(6)}.join }
- 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
Sidef
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."
- 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
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:")
Fmt.tprint("$,6d", results, 10)
System.print("\nFound %(results.count) such concatenated primes.")
- 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
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.
");
]
- 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.
- Draft Programming Tasks
- Prime Numbers
- 11l
- Action!
- Action! Tool Kit
- Action! Sieve of Eratosthenes
- Ada
- ALGOL 68
- ALGOL 68-primes
- ALGOL W
- Arturo
- AWK
- BASIC
- BASIC256
- FreeBASIC
- Yabasic
- C
- Delphi
- SysUtils,StdCtrls
- EasyLang
- Factor
- Go
- Go-rcu
- Haskell
- J
- Jq
- Julia
- Mathematica
- Wolfram Language
- Lua
- Nim
- Perl
- Phix
- PL/M
- Python
- Quackery
- Raku
- REXX
- Ring
- RPL
- Ruby
- Sidef
- Wren
- Wren-math
- Wren-fmt
- Wren-seq
- XPL0