65 lines
1.1 KiB
Text
65 lines
1.1 KiB
Text
F isProbablePrime(n, k = 10)
|
||
I n < 2 | n % 2 == 0
|
||
R n == 2
|
||
|
||
V d = n - 1
|
||
V s = 0
|
||
L d % 2 == 0
|
||
d I/= 2
|
||
s++
|
||
|
||
assert(2 ^ s * d == n - 1)
|
||
|
||
Int nn
|
||
I n < 7FFF'FFFF
|
||
nn = Int(n)
|
||
E
|
||
nn = 7FFF'FFFF
|
||
|
||
L(_) 0 .< k
|
||
V a = random:(2 .< nn)
|
||
V x = pow(a, d, n)
|
||
I x == 1 | x == n - 1
|
||
L.continue
|
||
L(_) 0 .< s - 1
|
||
x = pow(x, 2, n)
|
||
I x == 1
|
||
R 0B
|
||
I x == n - 1
|
||
L.break
|
||
L.was_no_break
|
||
R 0B
|
||
|
||
R 1B
|
||
|
||
F is_prime(a)
|
||
I a == 2
|
||
R 1B
|
||
I a < 2 | a % 2 == 0
|
||
R 0B
|
||
L(i) (3 .. Int(sqrt(a))).step(2)
|
||
I a % i == 0
|
||
R 0B
|
||
R 1B
|
||
|
||
V primorial = BigInt(1)
|
||
|
||
V nn = 50
|
||
V lim = 75
|
||
V s = Set[Int]()
|
||
L(n) 1..
|
||
I is_prime(n)
|
||
primorial *= n
|
||
V m = 3
|
||
L
|
||
I isProbablePrime(primorial + m, 25)
|
||
s.add(m)
|
||
L.break
|
||
m += 2
|
||
I --lim == 0
|
||
L.break
|
||
|
||
print(‘First ’nn‘ fortunate numbers:’)
|
||
L(m) sorted(Array(s))[0 .< nn]
|
||
V i = L.index
|
||
print(‘#3’.format(m), end' I (i + 1) % 10 == 0 {"\n"} E ‘ ’)
|