Untouchable numbers: Difference between revisions

Content added Content deleted
(Realize in F#)
(→‎{{header|Go}}: Updated version.)
Line 102: Line 102:
</pre>
</pre>
=={{header|Go}}==
=={{header|Go}}==
This was originally based on the Wren 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.
{{trans|Wren}}
<lang go>package main
<lang go>package main


Line 108: Line 108:


func sumDivisors(n int) int {
func sumDivisors(n int) int {
sum := 0
sum := 1
⚫
i := 1
k := 2
k := 2
if n%2 == 0 {
if n%2 == 0 {
k = 1
k = 1
}
}
for i*i <= n {
for i := 1 + k; i*i <= n; i += k {
if n%i == 0 {
if n%i == 0 {
sum += i
sum += i
Line 122: Line 121:
}
}
}
}
⚫
i += k
}
}
return sum - n
return sum
}
}


func sieve(n int) []bool {
func sieve(n int) []bool {
n++
n++
s := make([]bool, n*4) // all false by default
s := make([]bool, n+1) // all false by default
for i := 0; i <= n; i++ {
for i := 6; i <= n; i++ {
s[sumDivisors(i)] = true
sd := sumDivisors(i)
⚫
if sd <= n {
⚫
s[sd] = true
⚫
}
}
}
return s
return s
}
}


func isPrime(n int) bool {
func primeSieve(limit int) []bool {
if n < 2 {
limit++
return false
// True denotes composite, false denotes prime.
c := make([]bool, limit) // all false by default
}
if n%2 == 0 {
c[0] = true
return n == 2
c[1] = true
// no need to bother with even numbers over 2 for this task
}
if n%3 == 0 {
p := 3 // Start from 3.
return n == 3
for {
}
p2 := p * p
d := 5
if p2 >= limit {
for d*d <= n {
break
⚫
if n%d == 0 {
⚫
return false
}
}
d += 2
for i := p2; i < limit; i += 2 * p {
if n%d == 0 {
c[i] = true
return false
}
for {
⚫
p += 2
if !c[p] {
⚫
break
}
}
}
⚫
d += 4
}
}
return true
return c
}
}


Line 176: Line 179:


func main() {
func main() {
limit := 100000
c := primeSieve(1000000)
s := sieve(14 * limit)
limit := 1000000
s := sieve(63 * limit)
untouchable := []int{2, 5}
untouchable := []int{2, 5}
for n := 6; n <= limit; n += 2 {
for n := 6; n <= limit; n += 2 {
if !s[n] && !isPrime(n-1) && !isPrime(n-3) {
if !s[n] && c[n-1] && c[n-3] {
untouchable = append(untouchable, n)
untouchable = append(untouchable, n)
}
}
Line 193: Line 197:
count++
count++
}
}
fmt.Printf("\n\n%6s untouchable numbers were found <= 2,000\n", commatize(count))
fmt.Printf("\n\n%7s untouchable numbers were found <= 2,000\n", commatize(count))
p := 10
p := 10
count = 0
count = 0
Line 201: Line 205:
cc := commatize(count - 1)
cc := commatize(count - 1)
cp := commatize(p)
cp := commatize(p)
fmt.Printf("%6s untouchable numbers were found <= %7s\n", cc, cp)
fmt.Printf("%7s untouchable numbers were found <= %9s\n", cc, cp)
p = p * 10
p = p * 10
if p == limit {
if p == limit {
Line 210: Line 214:
cu := commatize(len(untouchable))
cu := commatize(len(untouchable))
cl := commatize(limit)
cl := commatize(limit)
fmt.Printf("%6s untouchable numbers were found <= %s\n", cu, cl)
fmt.Printf("%7s untouchable numbers were found <= %s\n", cu, cl)
}</lang>
}</lang>


Line 237: Line 241:
1,958 1,960 1,962 1,972 1,986 1,992
1,958 1,960 1,962 1,972 1,986 1,992


196 untouchable numbers were found <= 2,000
196 untouchable numbers were found <= 2,000
2 untouchable numbers were found <= 10
2 untouchable numbers were found <= 10
5 untouchable numbers were found <= 100
5 untouchable numbers were found <= 100
89 untouchable numbers were found <= 1,000
89 untouchable numbers were found <= 1,000
1,212 untouchable numbers were found <= 10,000
1,212 untouchable numbers were found <= 10,000
13,863 untouchable numbers were found <= 100,000
13,863 untouchable numbers were found <= 100,000
150,232 untouchable numbers were found <= 1,000,000
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Untouchable_numbers"