Numbers whose count of divisors is prime: Difference between revisions

← Older edit

Numbers whose count of divisors is prime (view source)

Revision as of 19:38, 20 February 2024

1,611 bytes removed , 3 months ago

m

→‎smarter, faster: extended desc

Petelomax

7,796

edits

Revision as of 11:46, 4 February 2024 (view source) Nig (talk \| contribs) m (→‎{{header\|AppleScript}}: Variable label changed. Source of squares-only idea acknowledged.) ← Older edit		Latest revision as of 19:38, 20 February 2024 (view source) Petelomax (talk \| contribs) m (→‎smarter, faster: extended desc)
(2 intermediate revisions by 2 users not shown)
Line 728: </pre> =={{header\|EasyLang}}== <~~!--</~~syntaxhighlight~~>--~~>▼ fastfunc isprim num . if num mod 2 = 0 return 0 . i = 3 while i <= sqrt num if num mod i = 0 return 0 . i += 2 . return 1 . for n to 999 cnt = 0 for m to n cnt += if n mod m = 0 . if cnt > 2 and isprim cnt = 1 write n & " " . . </syntaxhighlight> {{out}} <pre> 4 9 16 25 49 64 81 121 169 289 361 529 625 729 841 961 </pre> =={{header\|F_Sharp\|F#}}== Line 1,424 ⟶ 1,455: =={{header\|Phix}}== <!--~~<syntaxhighlight lang="phix">~~(phixonline)--> <syntaxhighlight lang="phix"> ~~<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>~~ atom t0 = time() <span style="color: #008080;">function</span> <span style="color: #000000;">pd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">return</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> function pd(integer n) n = length(factors(n,1)) return n!=2 and is_prime(n) end function <span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> for n in {1e3,1e5} do <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> sequence res = filter(tagset(n),pd) <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">pd</span><span style="color: #0000FF;">)</span> printf(1,"%d < %,d found: %v\n",{length(res),n,shorten(res,"",5)}) <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d < %,d found: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)})</span> end for ~~<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>~~ ?elapsed(time()-t0) ▲<!--</syntaxhighlight>--> </syntaxhighlight> {{out}} <pre> 16 < 1,000 found: {4,9,16,25,49,"...",529,625,729,841,961} 79 < 100,000 found: {4,9,16,25,49,"...",83521,85849,94249,96721,97969} "0.4s" </pre> === smarter, faster === As per Nigel's analysis on the talk page, valid numbers must be of the form a^(b-1) where a is prime and b is an odd prime, with no further checking required. <syntaxhighlight lang="phix"> atom t1 = time() for n in {1e3,1e5,4e9} do sequence r = {} for a in get_primes_le(floor(sqrt(n))) do integer b = 2 while true do atom c = power(a,get_prime(b)-1) if c>n then exit end if r &= c b += 1 end while end for r = sort(deep_copy(r)) printf(1,"%d < %,d found: %v\n",{length(r),n,shorten(r,"",5)}) end for ?elapsed(time()-t1) </syntaxhighlight> {{out}} <pre> 16 < 1,000 found: {4,9,16,25,49,"...",529,625,729,841,961} 79 < 100,000 found: {4,9,16,25,49,"...",83521,85849,94249,96721,97969} 6417 < 4,000,000,000 found: {4,9,16,25,49,"...",3991586041.0,3993860809.0,3994113601.0,3995630521.0,3999424081.0} "0.0s" </pre>