Super-Poulet numbers: Difference between revisions
Created Nim solution.
(→{{header|Ruby}}: Corrected output) |
(Created Nim solution.) |
||
Line 184:
The first super-Poulet number over 1 million is the 109th one, which is 1016801
The first super-Poulet number over 10 million is the 317th one, which is 10031653
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
proc powMod*(a, n, m: int): int =
## Return "a^n mod m".
var a = a mod m
var n = n
if a > 0:
result = 1
while n > 0:
if (n and 1) != 0:
result = (result * a) mod m
n = n shr 1
a = (a * a) mod m
func isPrime(n: Natural): bool =
## Return true if "n" is prime.
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
iterator divisors(n: Positive): int =
## Yield the divisors of "n", except 1.
yield n
var d = 2
while d * d <= n:
if n mod d == 0:
let q = n div d
yield d
if q != d:
yield q
inc d
func isSuperPouletNumber(n: int): bool =
## Return true is "x" is a Fermat pseudoprime to base "a".
if n.isPrime or powMod(2, n - 1, n) != 1: return false
for d in n.divisors:
if powMod(2, d, d) != 2:
return false
result = true
var n = 2
var count = 0
while true:
if n.isSuperPouletNumber:
inc count
if count <= 20:
stdout.write &"{n:5}"
stdout.write if count mod 5 == 0: '\n' else: ' '
if count == 20: echo()
elif n > 1_000_000:
echo &"First super-Poulet number greater than one million is {insertSep($n)} at index {count}."
break
inc n
</syntaxhighlight>
{{out}}
<pre> 341 1387 2047 2701 3277
4033 4369 4681 5461 7957
8321 10261 13747 14491 15709
18721 19951 23377 31417 31609
First super-Poulet number greater than one million is 1_016_801 at index 109.
</pre>
| |||