Untouchable numbers: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Sieve now uses less memory and primes are generated in advance. Timing still about 66 seconds.) |
(→{{header|F_Sharp|F#}}: Applied dendrology. Count to 2 million) |
||
| Line 66: | Line 66: | ||
This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]] |
This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]] |
||
<lang fsharp> |
<lang fsharp> |
||
// |
// Applied dendrology. Nigel Galloway: February 15., 2021 |
||
let fN i (g::e as l)=let rec fN n x=match n with h::t->(let n=x+h in if n>i then None else fN t n) |_->Some((if x+g>i then [] else l),int x) in fN e 0L |
let fN i (g::e as l)=let rec fN n x=match n with h::t->(let n=x+h in if n>i then None else fN t n) |_->Some((if x+g>i then [] else l),int x) in fN e 0L |
||
let fG n (i: |
let fG n (i:int64[]) g l=let mutable l=l-1 in (fun()->l<-l+1; if l<i.Length then (fN n ((((g|>List.map((*)(i.[l])))@g)|>List.distinct)),l) else (None,l)) |
||
let uT g=let N |
let uT g=let N,fN=Array.create(g+1) true,fG (int64 g) [|yield! primes64()|>Seq.takeWhile((>)(int64 g))|] |
||
let g= |
let rec fG n g=match n() with (Some([],z),_)->N.[z]<-false; fG n g |
||
|(Some(n,z),e) ->N.[z]<-false; let n=fN n e in fG n (n::g) |
|||
|_->match g with _::n::g->fG n (n::g) |_->N.[0]<-false; N |
|||
let n=fN [1L] 0 in fG n [n] |
|||
|_->match l with (n,e)::t->fG n e (if e<G.Length-1 then (n,e+1)::t else t) |_->() |
|||
N.[0]<-false; fG [1L] 0 [([1L],1)]; N |
|||
</lang> |
</lang> |
||
===The Task=== |
===The Task=== |
||
| Line 90: | Line 90: | ||
1542 1566 1578 1588 1596 1632 1642 1650 1680 1682 1692 1716 1718 1728 1732 1746 1758 1766 1774 1776 1806 1816 1820 1822 1830 1838 1840 1842 1844 1852 |
1542 1566 1578 1588 1596 1632 1642 1650 1680 1682 1692 1716 1718 1728 1732 1746 1758 1766 1774 1776 1806 1816 1820 1822 1830 1838 1840 1842 1844 1852 |
||
1860 1866 1884 1888 1894 1896 1920 1922 1944 1956 1958 1960 1962 1972 1986 1992 |
1860 1866 1884 1888 1894 1896 1920 1922 1944 1956 1958 1960 1962 1972 1986 1992 |
||
Real: 00:00:00. |
Real: 00:00:00.017, CPU: 00:00:00.015</pre> |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
<lang fsharp> |
<lang fsharp> |
||
printfn "%d" (uT 100000|>Array.filter id|>Array.length) |
printfn "%d" (uT 100000|>Array.filter id|>Array.length) |
||
| Line 99: | Line 98: | ||
<pre> |
<pre> |
||
13863 |
13863 |
||
Real: 00: |
Real: 00:00:05.396, CPU: 00:00:05.390</pre> |
||
| ⚫ | |||
;Count less than or equal 1000000 |
|||
<lang fsharp> |
|||
printfn "%d" (uT 1000000|>Array.filter id|>Array.length) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
150232 |
|||
Real: 00:06:40.494, CPU: 00:06:40.125 |
|||
</pre> |
|||
;Count less than or equal 2000000 |
|||
<lang fsharp> |
|||
printfn "%d" (uT 2000000|>Array.filter id|>Array.length) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
305290 |
|||
</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. |
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. |
||