Numbers whose count of divisors is prime: Difference between revisions
Numbers whose count of divisors is prime (view source)
Revision as of 19:38, 20 February 2024
, 3 months ago→smarter, faster: extended desc
(Added AppleScript.) |
m (→smarter, faster: extended desc) |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 163:
=={{header|AppleScript}}==
Only squares checked, as per the Discussion page.
<syntaxhighlight lang="applescript">on countFactors(n) -- Positive ns only.
if (n < 4) then return 2 - ((n = 1) as integer)
Line 189 ⟶ 190:
on task()
set limit to 100000 - 1
set
set inset to " "'s text 1 thru (
set output to {"Positive integers < " & (limit + 1) & " whose divisor count is an odd prime:"}
set row to {}
set counter to 0
repeat with
set
if (countFactors(countFactors(
set counter to counter + 1
set row's end to (inset &
if ((count row) = 10) then
set output's end to join(row, " ")
Line 727 ⟶ 728:
</pre>
=={{header|EasyLang}}==
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,423 ⟶ 1,455:
=={{header|Phix}}==
<!--
<syntaxhighlight lang="phix">
atom t0 = time()
function pd(integer n) n = length(factors(n,1)) return n!=2 and is_prime(n) end function
for n in {1e3,1e5} do
sequence res = filter(tagset(n),pd)
printf(1,"%d < %,d found: %v\n",{length(res),n,shorten(res,"",5)})
end for
?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>
|