Anonymous user
Strong and weak primes: Difference between revisions
→{{header|Nim}}
Line 1,167:
37780
321750</pre>
=={{header|Nim}}==
<lang Nim>import math, strutils
const
M = 10_000_000
N = M + 19 # Maximum value for sieve.
# Fill sieve of Erathosthenes.
var comp: array[2..N, bool] # True means composite; default is prime.
for n in countup(3, sqrt(N.toFloat).int, 2):
if not comp[n]:
for k in countup(n * n, N, n):
comp[k] = true
# Build list of primes.
var primes = @[2]
for n in countup(3, N, 2):
if not comp[n]:
primes.add n
if primes[^1] < M: quit "Not enough primes: please, increase value of N."
# Build lists of strong and weak primes.
var strongPrimes, weakPrimes: seq[int]
for i in 1..<primes.high:
let p = primes[i]
if p shl 1 > primes[i - 1] + primes[i + 1]:
strongPrimes.add p
elif p shl 1 < primes[i - 1] + primes[i + 1]:
weakPrimes.add p
when isMainModule:
proc count(list: seq[int]; max: int): int =
## Return the count of values less than "max".
for p in list:
if p >= max: break
inc result
echo "First 36 strong primes:"
echo " ", strongPrimes[0..35].join(" ")
echo "Count of strong primes below 1_000_000: ", strongPrimes.count(1_000_000)
echo "Count of strong primes below 10_000_000: ", strongPrimes.count(10_000_000)
echo()
echo "First 37 weak primes:"
echo " ", weakPrimes[0..36].join(" ")
echo "Count of weak primes below 1_000_000: ", weakPrimes.count(1_000_000)
echo "Count of weak primes below 10_000_000: ", weakPrimes.count(10_000_000)</lang>
{{out}}
<pre>First 36 strong primes:
11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439
Count of strong primes below 1_000_000: 37723
Count of strong primes below 10_000_000: 320991
First 37 weak primes:
3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181 193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401
Count of weak primes below 1_000_000: 37780
Count of weak primes below 10_000_000: 321750</pre>
=={{header|Pascal}}==
| |||