Untouchable numbers: Difference between revisions
→{{header|Go}}: Added a second much faster version.
m (Oops, removed duplicate Wren header.) |
(→{{header|Go}}: Added a second much faster version.) |
||
Line 569:
=={{header|Go}}==
===Version1 ===
This was originally based on the Wren Version 1 example but has been modified somewhat to find untouchable numbers up to 1 million rather than 100,000 in a reasonable time. On my machine, the former (with a sieve factor of 63) took 31 minutes 9 seconds and the latter (with a sieve factor of 14) took 6.2 seconds.
<syntaxhighlight lang="go">package main
Line 715 ⟶ 716:
13,863 untouchable numbers were found <= 100,000
150,232 untouchable numbers were found <= 1,000,000
</pre>
===Version 2===
{{trans|C}}
{{libheader|Go-rcu}}
This version uses a much more efficient algorithm for calculating the sums of divisors in bulk.
Run time for finding untouchable numbers up to 1 million is now only 11 seconds which (surprisingly) is faster than C itself on the same machine.
Also, since the first version was written, some of the functions used have now been incorporated into the above library.
<syntaxhighlight lang="go">package main
import (
"fmt"
"rcu"
)
func main() {
limit := 1000000
m := 63
c := rcu.PrimeSieve(limit, false)
n := m*limit + 1
sumDivs := make([]int, n)
for i := 1; i < n; i++ {
for j := i; j < n; j += i {
sumDivs[j] += i
}
}
s := make([]bool, n) // all false
for i := 1; i < n; i++ {
sum := sumDivs[i] - i // proper divs sum
if sum <= n {
s[sum] = true
}
}
untouchable := []int{2, 5}
for n := 6; n <= limit; n += 2 {
if !s[n] && c[n-1] && c[n-3] {
untouchable = append(untouchable, n)
}
}
fmt.Println("List of untouchable numbers <= 2,000:")
count := 0
for i := 0; untouchable[i] <= 2000; i++ {
fmt.Printf("%6s", rcu.Commatize(untouchable[i]))
if (i+1)%10 == 0 {
fmt.Println()
}
count++
}
fmt.Printf("\n\n%7s untouchable numbers were found <= 2,000\n", rcu.Commatize(count))
p := 10
count = 0
for _, n := range untouchable {
count++
if n > p {
cc := rcu.Commatize(count - 1)
cp := rcu.Commatize(p)
fmt.Printf("%7s untouchable numbers were found <= %9s\n", cc, cp)
p = p * 10
if p == limit {
break
}
}
}
cu := rcu.Commatize(len(untouchable))
cl := rcu.Commatize(limit)
fmt.Printf("%7s untouchable numbers were found <= %s\n", cu, cl)
}</syntaxhighlight>
{{out}}
<pre>
Same as Version 1.
</pre>
| |||