Rosetta Code

Numbers whose count of divisors is prime: Difference between revisions

Page Discussion

Numbers whose count of divisors is prime (view source)

Revision as of 19:29, 20 February 2024

2,175 bytes removed ,  3 months ago
m
→‎{{header|Phix}}: use pygments, added faster version to 4e9
(Added Easylang)
m (→‎{{header|Phix}}: use pygments, added faster version to 4e9)
Line 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 &lt; %,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
<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>
 
Petelomax
7,796

edits

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