Strong and weak primes: Difference between revisions
Content added Content deleted
Line 1,167: | Line 1,167: | ||
37780 |
37780 |
||
321750</pre> |
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}}== |
=={{header|Pascal}}== |