Safe primes and unsafe primes: Difference between revisions
→{{header|jq}}
Line 1,133:
Number of unsafe primes below 1,000,000: 74174
Number of unsafe primes below 10,000,000: 633922</pre>
=={{header|jq}}==
{{works with|jq}}
To save memory, we use a memory-less `is_prime` algorithm, but with a long preamble.
<lang jq>
def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
elif ($n % 23 == 0) then $n == 23
elif ($n % 29 == 0) then $n == 29
elif ($n % 31 == 0) then $n == 31
else 37
| until( (. * .) > $n or ($n % . == 0); . + 2)
| . * . > $n
end;
def task:
# a helper function for keeping count:
def record($p; counter6; counter7):
if $p < 10000000
then counter7 += 1
| if $p < 1000000
then counter6 += 1
else .
end
else .
end;
10000000 as $n
| reduce (2, range(3;$n;2)) as $p ({};
if $p|is_prime
then if (($p - 1) / 2) | is_prime
then if .safedone then .
else if .safeprimes|length < 35
then .safeprimes += [$p] | .safedone = (35 == (.safeprimes|length))
else .
end
end
| record($p; .nsafeprimes6; .nsafeprimes7)
else if .unsafedone then .
else if .unsafeprimes|length < 40
then .unsafeprimes += [$p] | .unsafedone = (40 == (.unsafeprimes|length))
else .
end
end
| record($p; .nunsafeprimes6; .nunsafeprimes7)
end
else .
end )
| "The first 35 safe primes are: ", .safeprimes[0:35],
"\nThere are \(.nsafeprimes6) safe primes less than 1 million.",
"\nThere are \(.nsafeprimes7) safe primes less than 10 million.",
"",
"\nThe first 40 unsafe primes are:", .unsafeprimes[0:40],
"\nThere are \(.nunsafeprimes6) unsafe primes less than 1 million.",
"\nThere are \(.nunsafeprimes7) unsafe primes less than 10 million."
;
task</lang>
{{out}}
<pre>
The first 35 safe primes are:
[5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619]
There are 4324 safe primes less than 1 million.
There are 30657 safe primes less than 10 million.
The first 40 unsafe primes are:
[2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233]
There are 74174 unsafe primes less than 1 million.
There are 633922 unsafe primes less than 10 million.
</pre>
=={{header|Julia}}==
| |||