Factors of an integer: Difference between revisions
Content added Content deleted
m (→Icon and Unicon: header simplification) |
(Go solution) |
||
Line 594: | Line 594: | ||
div2(Factorial(5)); |
div2(Factorial(5)); |
||
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]</lang> |
# [ 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}}== |
=={{Header|Haskell}}== |