Untouchable numbers: Difference between revisions
Added FreeBASIC
m (Oops, removed duplicate Wren header.) |
(Added FreeBASIC) |
||
| (4 intermediate revisions by one other user not shown) | |||
Line 184:
=={{header|C}}==
Run time around
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
Line 500:
readln;
end.</syntaxhighlight>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vbnet">Const max_untouchable = 1e6
Dim Shared untouchable(1 To max_untouchable) As Uinteger
For i As Uinteger = 1 To Ubound(untouchable)
untouchable(i) = True
Next i
Sub show_untouchable_statistics()
Dim As Uinteger i, cnt = 0
For i = 1 To Ubound(untouchable)
If untouchable(i) Then cnt += 1
If i = 10 Orelse i = 100 Orelse i = 1000 Orelse i = 10000 Orelse i = 1e5 Then
Print Using "###,### untouchable numbers were found <= #,###,###"; cnt; i
End If
Next i
End Sub
Sub print_untouchables(n As Uinteger)
Print Using "List of untouchable numbers <= #,###:"; n
Dim As Uinteger i, cnt = 0
For i = 1 To n
If untouchable(i) Then
Print Using "##,###"; i;
cnt += 1
Print Iif(cnt Mod 16 = 0, !"\n", " ");
End If
Next i
Print: Print
Print Using "###,### untouchable numbers were found <= #,###,###"; cnt; n
End Sub
Dim As Uinteger i, j
untouchable(1) = False
untouchable(3) = False
For i = 7 To Ubound(untouchable) Step 2
untouchable(i) = False
Next i
Dim Shared spd(1 To max_untouchable * 64) As Uinteger
Dim As Uinteger ub = Ubound(spd)
For i = 1 To ub
spd(i) = 1
Next i
For i = 2 To ub
For j = i + i To ub Step i
spd(j) += i
Next j
Next i
For i = 1 To ub
If spd(i) <= Ubound(untouchable) Then untouchable(spd(i)) = False
Next i
' Show the untouchable numbers up to 2000
print_untouchables(2000)
' Show the counts of untouchable numbers
show_untouchable_statistics()
Sleep</syntaxhighlight>
=={{header|F_Sharp|F#}}==
Line 569 ⟶ 629:
=={{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 ⟶ 776:
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>
Line 909 ⟶ 1,043:
=={{header|Nim}}==
I borrowed some ideas from Go version 1, but keep the limit to 100_000 as in Wren version 1.
<syntaxhighlight lang="nim">import math, strutils
Line 993 ⟶ 1,127:
There are 1212 untouchable numbers ≤ 10000.
There are 13863 untouchable numbers ≤ 100000.</pre>
=={{header|Pascal}}==
modified [[Factors_of_an_integer#using_Prime_decomposition]] to calculate only sum of divisors<BR>
Line 1,818 ⟶ 1,953:
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
Line 1,824 ⟶ 1,958:
===Version 1===
Run time about 70 seconds on my Core i7 machine.
<syntaxhighlight lang="
import "./
var sieve = Fn.new { |n|
Line 1,849 ⟶ 1,982:
System.print("List of untouchable numbers <= 2,000:")
System.print()
Fmt.print("$,6d untouchable numbers were found <= 2,000", untouchable.count { |n| n <= 2000 })
Line 1,903 ⟶ 2,034:
Run time for untouchable numbers up to 100,000 (m = 14) is now only 1.4 seconds and 1,000,000 (m = 63) is reached in 132 seconds.
<syntaxhighlight lang="
import "./
var limit = 1e6
Line 1,931 ⟶ 2,061:
}
System.print("List of untouchable numbers <= 2,000:")
System.print()
Fmt.print("$,7d untouchable numbers were found <= 2,000", untouchable.count { |n| n <= 2000 })
| |||