Home primes: Difference between revisions

=={{header|Nim}}==

{{trans|Wren}}

{{libheader|bignum}}

This algorithm is really efficient. We get the result for HP2 to HP20 in about 6 ms and adding HP65 in 1.3 s. I think that the threshold to switch to Pollard-Rho is very important.

<lang Nim>import algorithm, sequtils, strformat, strutils

import bignum

let

Two = newInt(2)

Three = newInt(3)

Five = newInt(5)

proc primeFactorsWheel(n: Int): seq[Int] =

const Inc = [4, 2, 4, 2, 4, 6, 2, 6]

var n = n

while (n mod 2).isZero:

result.add Two

n = n div 2

while (n mod 3).isZero:

result.add Three

n = n div 3

while (n mod 5).isZero:

result.add Five

n = n div 5

var k = 7

var i = 0

while k * k <= n:

if (n mod k).isZero:

result.add newInt(k)

n = n div k

else:

inc k, Inc[i]

i = (i + 1) and 7

if n > 1: result.add n

func pollardRho(n : Int): Int =

func g(x, y: Int): Int = (x * x + 1) mod y

var x, y = newInt(2)

var z, d = newInt(1)

var count = 0

while true:

x = g(x, n)

y = g(g(y, n), n)

d = abs(x - y) mod n

z *= d

inc count

if count == 100:

d = gcd(z, n)

if d != 1: break

z = newInt(1)

count = 0

if d == n: return newInt(0)

result = d

proc primeFactors(n: Int): seq[Int] =

var n = n

while n > 1:

if n > 100_000_000:

let d = pollardRho(n)

if not d.isZero:

result.add primeFactorsWheel(d)

n = n div d

if n.probablyPrime(25) != 0:

result.add n

break

else:

result.add primeFactorsWheel(n)

break

else:

result.add primeFactorsWheel(n)

break

result.sort()

let list = toSeq(2..20) & 65

for i in list:

if i in [2, 3, 5, 7, 11, 13, 17, 19]:

echo &"HP{i} = {i}"

continue

var n = 1

var j = newInt(i)

var h = @[j]

while true:

j = newInt(primeFactors(j).join())

h.add j

if j.probablyPrime(25) != 0:

for k in countdown(n, 1):

stdout.write &"HP{h[n-k]}({k}) = "

echo h[n]

break

else:

inc n</lang>

{{out}}

<pre>HP2 = 2

HP3 = 3

HP4(2) = HP22(1) = 211

HP5 = 5

HP6(1) = 23

HP7 = 7

HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5) = HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107

HP9(2) = HP33(1) = 311

HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773

HP11 = 11

HP12(1) = 223

HP13 = 13

HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367

HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129

HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373

HP17 = 17

HP18(1) = 233

HP19 = 19

HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413

HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11) = HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6) = HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2) = HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651</pre>