Super-Poulet numbers: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: Corrected output) |
(Created Nim solution.) |
||
Line 184: | Line 184: | ||
The first super-Poulet number over 1 million is the 109th one, which is 1016801 |
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 |
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> |
</pre> |
||