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
, 2 months ago→smarter, faster: extended desc
(add RPL) |
m (→smarter, faster: extended desc) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 161:
73441 76729 78961 80089 83521 85849 94249 96721 97969
</pre>
=={{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)
set factorCount to 2
set sqrt to n ^ 0.5
set limit to sqrt div 1
if (limit = sqrt) then
set factorCount to 3
set limit to limit - 1
end if
repeat with i from 2 to limit
if (n mod i = 0) then set factorCount to factorCount + 2
end repeat
return factorCount
end countFactors
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on task()
set limit to 100000 - 1
set nWidth to (count (limit as text))
set inset to " "'s text 1 thru (nWidth - 1)
set output to {"Positive integers < " & (limit + 1) & " whose divisor count is an odd prime:"}
set row to {}
set counter to 0
repeat with sqrt from 2 to (limit ^ 0.5 div 1)
set n to sqrt * sqrt
if (countFactors(countFactors(n)) = 2) then
set counter to counter + 1
set row's end to (inset & n)'s text -nWidth thru -1
if ((count row) = 10) then
set output's end to join(row, " ")
set row to {}
end if
end if
end repeat
if (row ≠ {}) then set output's end to join(row, " ")
set output's end to linefeed & counter & " such integers"
return join(output, linefeed)
end task
task()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"Positive integers < 100000 whose divisor count is an odd prime:
4 9 16 25 49 64 81 121 169 289
361 529 625 729 841 961 1024 1369 1681 1849
2209 2401 2809 3481 3721 4096 4489 5041 5329 6241
6889 7921 9409 10201 10609 11449 11881 12769 14641 15625
16129 17161 18769 19321 22201 22801 24649 26569 27889 28561
29929 32041 32761 36481 37249 38809 39601 44521 49729 51529
52441 54289 57121 58081 59049 63001 65536 66049 69169 72361
73441 76729 78961 80089 83521 85849 94249 96721 97969
79 such integers"</syntaxhighlight>
=={{header|Arturo}}==
Line 663 ⟶ 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 942 ⟶ 1,038:
52441 54289 57121 58081 59049 63001 65536 66049 69169 72361
73441 76729 78961 80089 83521 85849 94249 96721 97969</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
ispdc(n) = {
local(factors, ndivs);
factors = factor(n);
ndivs = numdiv(n);
ndivs > 2 && isprime(ndivs)
};
{
cnt=0;
for (i=1, 100000,
if (ispdc(i),
print1(i, " ");
cnt=cnt+1;
if(cnt%10==0,print(""));
);
);
}
</syntaxhighlight>
{{out}}
<pre>
4 9 16 25 49 64 81 121 169 289
361 529 625 729 841 961 1024 1369 1681 1849
2209 2401 2809 3481 3721 4096 4489 5041 5329 6241
6889 7921 9409 10201 10609 11449 11881 12769 14641 15625
16129 17161 18769 19321 22201 22801 24649 26569 27889 28561
29929 32041 32761 36481 37249 38809 39601 44521 49729 51529
52441 54289 57121 58081 59049 63001 65536 66049 69169 72361
73441 76729 78961 80089 83521 85849 94249 96721 97969
</pre>
=={{header|Pascal}}==
Line 1,324 ⟶ 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>
{{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>
Line 1,617 ⟶ 1,777:
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./
var limit = 1e5
Line 1,632 ⟶ 1,790:
}
Fmt.print("Positive integers under $,7d whose number of divisors is an odd prime:", limit)
Fmt.tprint("$,7d", results, 10)
var under1000 = results.count { |r| r < 1000 }
System.print("\nFound %(results.count) such integers (%(under1000) under 1,000).")</syntaxhighlight>
| |||