Home primes: Difference between revisions
Added Go
(→{{header|REXX}}: added the computer programming language REXX.) |
(Added Go) |
||
Line 89:
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
</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<lang go>package main
import (
"fmt"
"math/big"
"rcu"
"sort"
)
var zero = new(big.Int)
var one = big.NewInt(1)
var two = big.NewInt(2)
var three = big.NewInt(3)
var four = big.NewInt(4)
var five = big.NewInt(5)
var six = big.NewInt(6)
// simple wheel based prime factors routine for BigInt
func primeFactorsWheel(m *big.Int) []*big.Int {
n := new(big.Int).Set(m)
t := new(big.Int)
inc := []*big.Int{four, two, four, two, four, six, two, six}
var factors []*big.Int
for t.Rem(n, two).Cmp(zero) == 0 {
factors = append(factors, two)
n.Quo(n, two)
}
for t.Rem(n, three).Cmp(zero) == 0 {
factors = append(factors, three)
n.Quo(n, three)
}
for t.Rem(n, five).Cmp(zero) == 0 {
factors = append(factors, five)
n.Quo(n, five)
}
k := big.NewInt(7)
i := 0
for t.Mul(k, k).Cmp(n) <= 0 {
if t.Rem(n, k).Cmp(zero) == 0 {
factors = append(factors, new(big.Int).Set(k))
n.Quo(n, k)
} else {
k.Add(k, inc[i])
i = (i + 1) % 8
}
}
if n.Cmp(one) > 0 {
factors = append(factors, n)
}
return factors
}
func pollardRho(n *big.Int) *big.Int {
g := func(x, n *big.Int) *big.Int {
x2 := new(big.Int)
x2.Mul(x, x)
x2.Add(x2, one)
return x2.Mod(x2, n)
}
x, y, d := new(big.Int).Set(two), new(big.Int).Set(two), new(big.Int).Set(one)
t, z := new(big.Int), new(big.Int).Set(one)
count := 0
for {
x = g(x, n)
y = g(g(y, n), n)
t.Sub(x, y)
t.Abs(t)
t.Mod(t, n)
z.Mul(z, t)
count++
if count == 100 {
d.GCD(nil, nil, z, n)
if d.Cmp(one) != 0 {
break
}
z.Set(one)
count = 0
}
}
if d.Cmp(n) == 0 {
return new(big.Int)
}
return d
}
func primeFactors(m *big.Int) []*big.Int {
n := new(big.Int).Set(m)
var factors []*big.Int
lim := big.NewInt(1e9)
for n.Cmp(one) > 0 {
if n.Cmp(lim) > 0 {
d := pollardRho(n)
if d.Cmp(zero) != 0 {
factors = append(factors, primeFactorsWheel(d)...)
n.Quo(n, d)
if n.ProbablyPrime(10) {
factors = append(factors, n)
break
}
} else {
factors = append(factors, primeFactorsWheel(n)...)
break
}
} else {
factors = append(factors, primeFactorsWheel(n)...)
break
}
}
sort.Slice(factors, func(i, j int) bool { return factors[i].Cmp(factors[j]) < 0 })
return factors
}
func main() {
list := make([]int, 20)
for i := 2; i <= 20; i++ {
list[i-2] = i
}
list[19] = 65
for _, i := range list {
if rcu.IsPrime(i) {
fmt.Printf("HP%d = %d\n", i, i)
continue
}
n := 1
j := big.NewInt(int64(i))
h := []*big.Int{j}
for {
pf := primeFactors(j)
k := ""
for _, f := range pf {
k += fmt.Sprintf("%d", f)
}
j, _ = new(big.Int).SetString(k, 10)
h = append(h, j)
if j.ProbablyPrime(10) {
for l := n; l > 0; l-- {
fmt.Printf("HP%d(%d) = ", h[n-l], l)
}
fmt.Println(h[n])
break
} else {
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>
| |||