Concatenate two primes is also prime: Difference between revisions
Content added Content deleted
(→J: add) |
(Added Lua) |
||
Line 877: | Line 877: | ||
{{out}} |
{{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>{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> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |