Rosetta Code

Untouchable numbers: Difference between revisions

Page Discussion

Untouchable numbers (view source)

Revision as of 13:02, 17 February 2021

182 bytes added ,  3 years ago
→‎{{header|F_Sharp|F#}}: Applied dendrology. Count to 2 million
(→‎{{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:
This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]]
<lang fsharp>
// UntouchableApplied numbersdendrology. Nigel Galloway: JanuaryFebruary 31st15., 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 fG n (i::int64[]) g asl=let e)mutable l=l-1 in (fun()->l<-l+1; if l<i.Length then (fN n (((e(g|>List.map((*)(i.[l])))@eg)|>List.distinct)),l) else (None,l))
let uT g=let N,G,fN=Array.create (g+1) true,fG (int64 g) [|yield! primes64()|>Seq.takeWhile((>)(int64 g))|],fG (int64(g-1))
let rec fG n g=Gmatch n() with (Some([],z),_)->N.Length[z]<-1false; fG n g
let rec fG n e l=match fN n G.[e] with |(Some([]n,z),e) ->N.[z]<-false; matchlet l with (n,e)::t->fG=fN n e (ifin e<G.Length-1fG thenn (n,e+1)::t else t) |_->(g)
|_->match g with _::n::g->fG n |Some(n,z::g) |_->N.[z0]<-false; fG n e (if e<G.Length-1 then (n,e+1)::l else l)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>
===The Task===
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
1860 1866 1884 1888 1894 1896 1920 1922 1944 1956 1958 1960 1962 1972 1986 1992
Real: 00:00:00.229017, CPU: 00:00:00.218, GC gen0: 141, gen1: 3, gen2: 1015</pre>
;Count less than or equal 100000▼
</pre>▼
▲;Count less than 100000
<lang fsharp>
printfn "%d" (uT 100000|>Array.filter id|>Array.length)
Line 99 ⟶ 98:
<pre>
13863
Real: 00:0700:1205.230396, CPU: 00:0700:1105.921, GC gen0: 341102, gen1: 43, gen2: 4390</pre>
▲</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>
 
=={{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.
Nigel Galloway
2,172

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/307821"