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
m (C++ - restored accidentally deleted line) |
m (→smarter, faster: extended desc) |
||
| (33 intermediate revisions by 26 users not shown) | |||
Line 1:
{{Draft task|Prime Numbers}}
;Task:
Line 7:
Stretch goal: (as above), but where '''n < 100,000'''.
<br><br>
=={{header|11l}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="11l">F is_prime(a)
I a == 2
R 1B
I a < 2 | a % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
print(‘Numbers which count of divisors is prime are:’)
V row = 0
L(n) 1..99999
V num = 0
L(m) 1 .. n
I n % m == 0
num++
I is_prime(num) & num != 2
print(‘#6’.format(n), end' ‘ ’)
row++
I row % 5 == 0
print()
print("\n\nFound "row‘ numbers’)</syntaxhighlight>
{{out}}
<pre>
Numbers which count of divisors is prime are:
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
Found 79 numbers
</pre>
=={{header|Action!}}==
{{libheader|Action! Sieve of Eratosthenes}}
<syntaxhighlight lang="action!">INCLUDE "H6:SIEVE.ACT"
INT FUNC CountDivisors(INT x)
INT i,max,count
count=2 i=2 max=x
WHILE i<max
DO
IF x MOD i=0 THEN
max=x/i
IF i<max THEN
count==+2
ELSEIF i=max THEN
count==+1
FI
FI
i==+1
OD
RETURN (count)
PROC Main()
DEFINE MAXNUM="999"
BYTE ARRAY primes(MAXNUM+1)
INT i,count
Put(125) PutE() ;clear the screen
Sieve(primes,MAXNUM+1)
FOR i=2 TO MAXNUM
DO
IF primes(i)=0 THEN
count=CountDivisors(i)
IF count>2 AND primes(count)=1 THEN
PrintF("%I has %I divisors%E",i,count)
FI
FI
OD
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Numbers_whose_count_of_divisors_is_prime.png Screenshot from Atari 8-bit computer]
<pre>
4 has 3 divisors
9 has 3 divisors
16 has 5 divisors
25 has 3 divisors
49 has 3 divisors
64 has 7 divisors
81 has 5 divisors
121 has 3 divisors
169 has 3 divisors
289 has 3 divisors
361 has 3 divisors
529 has 3 divisors
625 has 5 divisors
729 has 7 divisors
841 has 3 divisors
961 has 3 divisors
</pre>
=={{header|ALGOL 68}}==
Counts the divisors without using division.
<
INT max number := 1 000;
TO 2 DO
Line 32 ⟶ 145:
max number := 100 000
OD
END</
{{out}}
<pre>
Line 48 ⟶ 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}}==
<syntaxhighlight lang="arturo">numsWithPrimeNofDivisors: select 1..100000 'x [
nofDivisors: size factors x
and? [prime? nofDivisors]
[nofDivisors <> 2]
]
loop split.every: 5 numsWithPrimeNofDivisors 'x ->
print map x 's -> pad to :string s 6</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|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f NUMBERS_WHOSE_COUNT_OF_DIVISORS_IS_PRIME.AWK
BEGIN {
start = 2
stop = 99999
stop2 = 999
for (i=start; i*i<=stop; i++) {
n = count_divisors(i*i)
if (n>2 && is_prime(n)) {
printf("%6d%1s",i*i,++count%10?"":"\n")
if (i*i <= stop2) {
count2++
}
}
}
printf("\nNumbers with odd prime divisor counts %d-%d: %d\n",start,stop2,count2)
printf("Numbers with odd prime divisor counts %d-%d: %d\n",start,stop,count)
exit(0)
}
function count_divisors(n, count,i) {
for (i=1; i*i<=n; i++) {
if (n % i == 0) {
count += (i == n / i) ? 1 : 2
}
}
return(count)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
</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
Numbers with odd prime divisor counts 2-999: 16
Numbers with odd prime divisor counts 2-99999: 79
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">function isPrime(v)
if v < 2 then return False
if (v mod 2) = 0 then return v = 2
if (v mod 3) = 0 then return v = 3
d = 5
while d * d <= v
if (v mod d) = 0 then return False else d = d + 2
end while
return True
end function
row = 0
print "Numbers which count of divisors is prime are:"
for n = 1 to 1000
num = 0
for m = 1 to n
if (n mod m) = 0 then num = num + 1
next m
if isPrime(num) and num <> 2 then
print ""; n; " ";
row = row + 1
end if
next n
print
print "Found "; row; " numbers"
end</syntaxhighlight>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">Function isPrime(Byval ValorEval As Integer) As Boolean
If ValorEval < 2 Then Return False
If ValorEval Mod 2 = 0 Then Return ValorEval = 2
If ValorEval Mod 3 = 0 Then Return ValorEval = 3
Dim d As Integer = 5
While d * d <= ValorEval
If ValorEval Mod d = 0 Then Return False Else d += 2
Wend
Return True
End Function
Dim As Integer row = 0
Dim As Uinteger n, num, m
Print "Numbers which count of divisors is prime are:"
For n = 1 To 100000
num = 0
For m = 1 To n
If n Mod m = 0 Then num += 1 : End If
Next m
If isPrime(num) And num <> 2 Then
Print Using " ##### "; n;
row += 1
If row Mod 5 = 0 Then Print : End If
End If
Next n
Print !"\n\nFound"; row; " numbers"
Sleep</syntaxhighlight>
{{out}}
<pre>Numbers which count of divisors is prime are:
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
Found 79 numbers</pre>
==={{header|QBasic}}===
{{works with|QBasic}}
{{works with|QuickBasic}}
{{trans|FreeBASIC}}
<syntaxhighlight lang="qbasic">row = 0
PRINT "Numbers which count of divisors is prime are:"
FOR n = 1 TO 1000
num = 0
FOR m = 1 TO n
IF n MOD m = 0 THEN num = num + 1
NEXT m
IF isPrime(num) AND num <> 2 THEN
PRINT USING " ##### "; n;
row = row + 1
IF row MOD 5 = 0 THEN PRINT
END IF
NEXT n
PRINT : PRINT "Found"; row; " numbers"
Sleep
END
FUNCTION isPrime (ValorEval)
IF ValorEval < 2 THEN isPrime = False
IF ValorEval MOD 2 = 0 THEN isPrime = 2
IF ValorEval MOD 3 = 0 THEN isPrime = 3
d = 5
WHILE d * d <= ValorEval
IF ValorEval MOD d = 0 THEN isPrime = False ELSE d = d + 2
WEND
isPrime = True
END FUNCTION</syntaxhighlight>
==={{header|PureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="purebasic">Procedure isPrime(v.i)
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
OpenConsole()
fila.i = 0
PrintN("Numbers which count of divisors is prime are:")
For n.i = 1 To 100000
num.i = 0
For m.i = 1 To n
If Mod(n, m) = 0
num + 1
EndIf
Next
If isPrime(num) And num <> 2
Print(" " + Str(n) + " ")
fila + 1
If Mod(fila, 5) = 0
PrintN("")
EndIf
EndIf
Next
PrintN(#CRLF$ + "Found " + Str(fila) + " numbers")
Input()
CloseConsole()
End</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">row = 0
print "Numbers which count of divisors is prime are:"
for n = 1 to 1000
num = 0
for m = 1 to n
if mod(n, m) = 0 then num = num + 1 : fi
next m
if isPrime(num) and num <> 2 then
print n using "#####",
row = row + 1
if mod(row, 5) = 0 then print : fi
end if
next n
print "\n\nFound ", row, " numbers"
end
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
end while
return True
end sub</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
=={{header|C++}}==
<
#include <cstdlib>
#include <iomanip>
Line 115 ⟶ 581:
std::cout << "\nCount: " << count << '\n';
return EXIT_SUCCESS;
}</
{{out}}
Line 136 ⟶ 602:
73441 76729 78961 80089 83521 85849 94249 96721 97969
Count: 79
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Find the amount of divisors for 1..N
div_counts = proc (n: int) returns (sequence[int])
divs: array[int] := array[int]$fill(1,n,1)
for d: int in int$from_to(2, n) do
for m: int in int$from_to_by(d, n, d) do
divs[m] := divs[m] + 1
end
end
return(sequence[int]$a2s(divs))
end div_counts
% Find maximum element of sequence
max = proc (seq: sequence[int]) returns (int)
n: int := 0
for i: int in sequence[int]$elements(seq) do
if i>n then n:=i end
end
return(n)
end max
% Sieve primes up to N
sieve = proc (n: int) returns (sequence[bool])
prime: array[bool] := array[bool]$fill(1,n,true)
prime[1] := false
for p: int in int$from_to(2, n/2) do
for c: int in int$from_to_by(p*p, n, p) do
prime[c] := false
end
end
return(sequence[bool]$a2s(prime))
end sieve
start_up = proc ()
MAX_N = 100000
po: stream := stream$primary_output()
div_count: sequence[int] := div_counts(MAX_N)
prime: sequence[bool] := sieve(max(div_count))
count: int := 0
for i: int in int$from_to(1, MAX_N) do
dc: int := div_count[i]
if dc ~= 2 cand prime[dc] then
stream$putright(po, int$unparse(i), 8)
count := count + 1
if count//10 = 0 then stream$putl(po, "") end
end
end
stream$putl(po, "\nFound " || int$unparse(count) || " numbers.")
end start_up</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
Found 79 numbers.</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
procedure GetUniqueFactors(N: integer; var IA: TIntegerDynArray);
{Get unique factors of a number}
var I: integer;
begin
SetLength(IA,1);
for I:=2 to N do
if (N mod I)=0 then
begin
SetLength(IA,Length(IA)+1);
IA[High(IA)]:=I;
end;
end;
procedure ShowCountPrimes(Memo: TMemo);
{Count the number of Unique factors that are prime}
var I,C,Cnt: integer;
var IA: TIntegerDynArray;
var S: string;
begin
Cnt:=0; S:='';
for I:=1 to 100000-1 do
begin
GetUniqueFactors(I,IA);
C:=Length(IA);
if (C=2) or (not IsPrime(C)) then continue;
Inc(Cnt);
S:=S+Format('%8D',[I]);
If (Cnt mod 5)=0 then S:=S+CRLF;
end;
Memo.Lines.Add('Count='+IntToStr(Cnt));
Memo.Lines.Add(S);
end;
</syntaxhighlight>
{{out}}
<pre>
Count=79
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
Elapsed Time: 17.921 Sec.
</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#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// Numbers whose divisor count is prime. Nigel Galloway: July 13th., 2021
primes64()|>Seq.takeWhile(fun n->n*n<100000L)|>Seq.collect(fun n->primes32()|>Seq.skip 1|>Seq.map(fun g->pown n (g-1))|>Seq.takeWhile((>)100000L))|>Seq.sort|>Seq.iter(printf "%d "); printfn ""
</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|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<syntaxhighlight lang="factor">USING: formatting grouping io kernel math math.primes
math.primes.factors math.ranges sequences sequences.extras ;
FROM: math.extras => integer-sqrt ;
: odd-prime? ( n -- ? ) dup 2 = [ drop f ] [ prime? ] if ;
: pdc-upto ( n -- seq )
integer-sqrt [1,b]
[ sq ] [ divisors length odd-prime? ] map-filter ;
100,000 pdc-upto 10 group [ [ "%-8d" printf ] each nl ] each</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|Go}}==
{{libheader|Go-rcu}}
<
import (
Line 188 ⟶ 846:
}
fmt.Printf("\n\nFound %d such integers (%d under 1,000).\n", len(results), under1000)
}</
{{out}}
Line 203 ⟶ 861:
Found 79 such integers (16 under 1,000).
</pre>
=={{header|J}}==
To find the divisors of a number we can use any of the implementations defined at in the [[Factors_of_an_integer#J|Factors of an integer]] task: <code>foi</code>, <code>factrs</code>, <code>factrst</code>, <code>factorsOfNumber</code> or <code>factors</code>. Here, we will use <code>factors</code> as it's the most efficient:
<syntaxhighlight lang=J>
(#~ (2&< * 1&p:)@#@factors"0) }. i. 100000
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
</syntaxhighlight>
(Note that we first conditioned J's environment to show longer lines, using [https://www.jsoftware.com/help/dictionary/dx009.htm#36 <code>9!:37(10*9!:36'')</code>].)
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
For a suitable definition of `is_prime`, see [[Erd%C5%91s-primes#jq]].
<syntaxhighlight lang="jq">def add(s): reduce s as $x (null; .+$x);
def count_divisors:
add(
if . == 1 then 1
else . as $n
| label $out
| range(1; $n) as $i
| ($i * $i) as $i2
| if $i2 > $n then break $out
else if $i2 == $n
then 1
elif ($n % $i) == 0
then 2
else empty
end
end
end);
1000, 100000
| "\nn with odd prime divisor counts, 1 < n < \(.):",
(range(1;.) | select(count_divisors | (. > 2 and is_prime)))</syntaxhighlight>
{{out}}
<pre>
n with odd prime divisor counts, 1 < n < 1000:
4
9
16
25
49
64
81
121
169
289
361
529
625
729
841
961
n with odd prime divisor counts, 1 < n < 100000:
4
9
....
85849
94249
96721
97969
</pre>
=={{header|Julia}}==
<
ispdc(n) = (ndivs = prod(collect(values(factor(n))).+ 1); ndivs > 2 && isprime(ndivs))
foreach(p -> print(rpad(p[2], 8), p[1] % 10 == 0 ? "\n" : ""), enumerate(filter(ispdc, 1:100000)))
</
<pre>
4 9 16 25 49 64 81 121 169 289
Line 221 ⟶ 947:
52441 54289 57121 58081 59049 63001 65536 66049 69169 72361
73441 76729 78961 80089 83521 85849 94249 96721 97969
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">max = 100000;
maxPrime = NextPrime[Sqrt@max, -1];
maxPower = NextPrime[Log[2, max], -1];
base = NestWhileList[NextPrime, 2, # < maxPrime &];
g = NestWhileList[NextPrime, 3, # < maxPower &] - 1;
ans = Sort@Select[Flatten@Table[base^n, {n, g}], # < max &];
Labeled[Partition[Select[ans, # < 1000 &], UpTo[8]] //
TableForm, "Numbers up to 1000 with prime divisor counts:", Top]
Labeled[Partition[ans, UpTo[8]] //
TableForm, "Numbers up to 100,000 with prime divisor counts:", Top]</syntaxhighlight>
{{out}}<pre>
Numbers up to 1000 with prime divisor counts:
4 9 16 25 49 64 81 121
169 289 361 529 625 729 841 961
Numbers up to 100,000 with prime divisor counts:
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 66049 69169 72361 73441 76729 78961
80089 83521 85849 94249 96721 97969
</pre>
Line 226 ⟶ 981:
Checking only divisors of squares (see discussion).
<
Line 268 ⟶ 1,023:
for i, n in list:
stdout.write &"{n:5}", if (i + 1) mod 10 == 0: '\n' else: ' '
echo()</
{{out}}
Line 283 ⟶ 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}}==
<
{$IFDEF FPC}
// {$R+,O+} //debuging purpose
Line 621 ⟶ 1,411:
writeln;
SpeedTest(pD,4000*1000*1000);
END.</
{{out}}
<pre> 1 2 3 4 5 6 7 8 9 10
Line 645 ⟶ 1,435:
SpeedTest 0.230 secs for 1..4000000000 found 6417</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use ntheory <is_prime divisors>;
push @matches, $_**2 for grep { is_prime divisors $_**2 } 1..int sqrt 1e5;
print @matches . " matching:\n" . (sprintf "@{['%6d' x @matches]}", @matches) =~ s/(.{72})/$1\n/gr;</syntaxhighlight>
{{out}}
<pre>79 matching:
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|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>
=={{header|Quackery}}==
Noting that only perfect squares can fit the criteria (see discussion).
<code>factors</code> and <code>isqrt</code> are defined at [[Factors of an integer#Quackery]].
<syntaxhighlight lang="Quackery"> [ dip number$
over size -
space swap of
swap join echo$ ] is recho ( n n --> )
[ []
100000 isqrt drop times
[ i^ dup * factors size
dup 2 = iff drop done
factors size 2 = while
i^ dup * join ] ]
[ dup [] != while
10 split swap
witheach [ 6 recho ]
cr again ]
drop</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|Raku}}==
<syntaxhighlight lang="raku"
my $ceiling = ceiling sqrt 1e5;
say display
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n" ) {
cache $
}</
{{out}}
<pre>79 matching:
Line 685 ⟶ 1,559:
=={{header|REXX}}==
<syntaxhighlight lang="rexx">/*REXX pgm finds positive integers N whose # of divisors is prime (& ¬=2), where N<1000.*/
parse arg hi cols . /*obtain optional arguments from the CL*/
if hi=='' | hi=="," then hi= 1000 /*Not specified? Then use the defaults*/
Line 696 ⟶ 1,569:
say ' index │'center(title, 1 + cols*(w+1) )
say '───────┼'center("" , 1 + cols*(w+1), '─')
finds= 0; idx= 1;
do j=
if \!.n then iterate /*Number divisors prime? No, then skip*/
finds= finds + 1 /*bump the number of found numbers. */
$= $ right( commas(j), w) /*add a positive integer ──► $ list. */
Line 737 ⟶ 1,607:
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 767 ⟶ 1,637:
=={{header|Ring}}==
<
load "stdlib.ring"
row = 0
Line 792 ⟶ 1,662:
see nl + "Found " + row + " numbers" + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 803 ⟶ 1,673:
Found 16 numbers
done...
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ { }
1 999 '''FOR''' j
j DIVIS SIZE
'''IF''' DUP 2 == '''THEN''' DROP '''ELSE'''
'''IF''' ISPRIME? '''THEN''' j + '''END'''
'''END'''
'''NEXT'''
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1; { 4 9 16 25 49 64 81 121 169 289 361 529 625 729 841 961 }
</pre>
Runs in 2 minutes 16 seconds on a HP-50g.
=={{header|Rust}}==
<syntaxhighlight lang="rust">
fn count_divisors(number : u64 ) -> u64 {
let mut divisors : u64 = 0 ;
for n in 1..=number {
if number % n == 0 {
divisors += 1 ;
}
}
divisors
}
fn main() {
let mut the_numbers : Vec<u64> = Vec::new( ) ;
let mut count : i32 = 0 ;
for n in 1..100000 {
let divis = count_divisors( n as u64 ) ;
if divis > 2 && primal::is_prime( divis ) {
the_numbers.push( n ) ;
}
}
for n in the_numbers {
count += 1 ;
print!(" {:6}" , n ) ;
if count % 8 == 0 {
println!( ) ;
}
}
println!( ) ;
println!("count is {}" , count) ;
}</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
count is 79
</pre>
=={{header|Ruby}}==
Testing squares only, according to observation on the discussion page.
<syntaxhighlight lang="ruby">require 'prime'
def tau(n) = n.prime_division.inject(1){|res, (d, exp)| res *= exp+1}
res = (1..Integer.sqrt(100_000)).filter_map{|n| sqr = n*n; sqr if tau(sqr).prime? }
res.each_slice(10){|slice| puts "%10d"*slice.size % slice}</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|Sidef}}==
<syntaxhighlight lang="ruby">var limit = 100_000
say "Positive integers under #{limit.commify} whose number of divisors is an odd prime:"
1..limit -> grep { !.is_prime && .sigma0.is_prime }.each_slice(10, {|*a|
say a.map{'%6s' % _}.join(' ')
})</syntaxhighlight>
{{out}}
<pre>
Positive integers under 100,000 whose number of divisors 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
</pre>
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./
var limit = 1e5
Line 822 ⟶ 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).")</
{{out}}
Line 839 ⟶ 1,807:
Found 79 such integers (16 under 1,000).
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true;
];
func Divisors(N); \Return number of unique divisors of N
int N, SN, Count, D;
[SN:= sqrt(N); \N must be a perfect square to get an odd (prime>2) count
if SN*SN # N then return 0;
Count:= 3; \SN, 1 and N are unique divisors of N >= 4
for D:= 2 to SN-1 do
if rem(N/D) = 0 then Count:= Count+2;
return Count;
];
int N, Count;
[Count:= 0;
for N:= 4 to 100_000-1 do
if IsPrime(Divisors(N)) then
[Count:= Count+1;
IntOut(0, N);
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
]</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>
| |||