Anonymous user
Safe primes and unsafe primes: Difference between revisions
→{{header|Nim}}
No edit summary |
|||
Line 1,332:
74174
633922</pre>
=={{header|Nim}}==
<lang Nim>import sequtils, strutils
const N = 10_000_000
# Erathostene's Sieve. Only odd values are represented. False value means prime.
var sieve: array[N div 2 + 1, bool]
sieve[0] = true # 1 is not prime.
for i in 1..sieve.high:
if not sieve[i]:
let n = 2 * i + 1
for k in countup(n * n, N, 2 * n):
sieve[k shr 1] = true
proc isprime(n: Positive): bool =
## Check if a number is prime.
n == 2 or (n and 1) != 0 and not sieve[n shr 1]
proc classifyPrimes(): tuple[safe, unsafe: seq[int]] =
## Classify prime numbers in safe and unsafe numbers.
for n in 2..N:
if n.isprime():
if (n shr 1).isprime():
result[0].add n
else:
result[1].add n
when isMainModule:
let (safe, unsafe) = classifyPrimes()
echo "First 35 safe primes:"
echo safe[0..<35].join(" ")
echo "Count of safe primes below 1_000_000:",
($safe.filterIt(it < 1_000_000).len).insertSep(',').align(7)
echo "Count of safe primes below 10_000_000:",
($safe.filterIt(it < 10_000_000).len).insertSep(',').align(7)
echo "First 40 unsafe primes:"
echo unsafe[0..<40].join(" ")
echo "Count of unsafe primes below 1_000_000:",
($unsafe.filterIt(it < 1_000_000).len).insertSep(',').align(8)
echo "Count of unsafe primes below 10_000_000:",
($unsafe.filterIt(it < 10_000_000).len).insertSep(',').align(8)</lang>
{{out}}
<pre>First 35 safe primes:
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
Count of safe primes below 1_000_000: 4,324
Count of safe primes below 10_000_000: 30,657
First 40 unsafe primes:
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
Count of unsafe primes below 1_000_000: 74,174
Count of unsafe primes below 10_000_000: 633,922</pre>
=={{header|Pascal}}==
| |||