Concatenate two primes is also prime: Difference between revisions
Content added Content deleted
(Added Algol 68) |
(Added Algol W) |
||
Line 43: | Line 43: | ||
print( ( newline, newline, "Found ", whole( c count, 0 ), " concat primes", newline ) ) |
print( ( newline, newline, "Found ", whole( c count, 0 ), " concat primes", newline ) ) |
||
END</lang> |
END</lang> |
||
{{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> |
|||
=={{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. |
|||
<lang algolw>begin % find primes whose decimal representation is the concatenation of 2 primes % |
|||
integer MAX_PRIME; |
|||
MAX_PRIME := 99 * 99; |
|||
begin |
|||
logical array isPrime ( 1 :: MAX_PRIME ); |
|||
logical array concatPrime ( 1 :: MAX_PRIME ); |
|||
integer cCount; |
|||
% sieve the primes to MAX_PRIME % |
|||
isPrime( 1 ) := false; isPrime( 2 ) := true; |
|||
for i := 3 step 2 until MAX_PRIME do isPrime( i ) := true; |
|||
for i := 4 step 2 until MAX_PRIME do isPrime( i ) := false; |
|||
for i := 3 step 2 until truncate( sqrt( MAX_PRIME ) ) do begin |
|||
integer ii; ii := i + i; |
|||
if isPrime( i ) then for pr := i * i step ii until MAX_PRIME do isPrime( pr ) := false |
|||
end for_i ; |
|||
% find the concatenated primes, note their final digit can't be 2 or 5 % |
|||
for i := 1 until MAX_PRIME do concatPrime( i ) := false; |
|||
cCount := 0; |
|||
for p1 := 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 |
|||
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 do begin |
|||
for p2 := 3, 7, 11, 13, 17, 19, 23, 29, 31, 37 |
|||
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 do begin |
|||
integer pc; |
|||
pc := ( p1 * ( if p2 < 10 then 10 else 100 ) ) + p2; |
|||
concatPrime( pc ) := isPrime( pc ) |
|||
end for_p2 |
|||
end for_p1; |
|||
% print the concatenated primes % |
|||
cCount := 0; |
|||
for i := 1 until MAX_PRIME do begin |
|||
if concatPrime( i ) then begin |
|||
writeon( i_w := 5, s_w := 0, i ); |
|||
cCount := cCount + 1; |
|||
if cCount rem 10 = 0 then write() |
|||
end if_concatPrime_i |
|||
end for_i; |
|||
write();write( i_w := 1, s_w := 0, "Found ", cCount, " concat primes" ) |
|||
end |
|||
end.</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |