Factors of an integer: Difference between revisions
Go solution
m (→Icon and Unicon: header simplification) |
(Go solution) |
||
Line 594:
div2(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]</lang>
=={{header|Go}}==
Trial division, no prime number generator, but with some optimizations. It's good enough to factor any 64 bit integer, with large primes taking several seconds.
<lang go>package main
import "fmt"
func main() {
printFactors(-1)
printFactors(0)
printFactors(1)
printFactors(2)
printFactors(3)
printFactors(53)
printFactors(45)
printFactors(64)
printFactors(600851475143)
printFactors(999999999999999989)
}
func printFactors(nr int64) {
if nr < 1 {
fmt.Println("\nFactors of", nr, "not computed")
return
}
fmt.Printf("\nFactors of %d: ", nr)
fs := make([]int64, 1)
fs[0] = 1
apf := func(p int64, e int) {
n := len(fs)
for i, pp := 0, p; i < e; i, pp = i+1, pp*p {
for j := 0; j < n; j++ {
fs = append(fs, fs[j]*pp)
}
}
}
e := 0
for ; nr & 1 == 0; e++ {
nr >>= 1
}
apf(2, e)
for d := int64(3); nr > 1; d += 2 {
if d*d > nr {
d = nr
}
for e = 0; nr%d == 0; e++ {
nr /= d
}
if e > 0 {
apf(d, e)
}
}
fmt.Println(fs)
fmt.Println("Number of factors =", len(fs))
}</lang>
Output:
<pre>Factors of -1 not computed
Factors of 0 not computed
Factors of 1: [1]
Number of factors = 1
Factors of 2: [1 2]
Number of factors = 2
Factors of 3: [1 3]
Number of factors = 2
Factors of 53: [1 53]
Number of factors = 2
Factors of 45: [1 3 9 5 15 45]
Number of factors = 6
Factors of 64: [1 2 4 8 16 32 64]
Number of factors = 7
Factors of 600851475143: [1 71 839 59569 1471 104441 1234169 87625999 6857 486847 5753023 408464633 10086647 716151937 8462696833 600851475143]
Number of factors = 16
Factors of 999999999999999989: [1 999999999999999989]
Number of factors = 2</pre>
=={{Header|Haskell}}==
| |||