Numbers whose count of divisors is prime
- Task
Find positive integers n which count of divisors is prime, but not equal to 2, where n < 1,000.
Stretch goal: (as above), but where n < 100,000.
ALGOL 68
Counts the divisors without using division. <lang algol68>BEGIN # find numbers with prime divisor counts #
INT max number := 1 000;
TO 2 DO
INT max divisors := 0;
# construct a table of the divisor counts #
[ 1 : max number ]INT ndc; FOR i FROM 1 TO UPB ndc DO ndc[ i ] := 1 OD;
FOR i FROM 2 TO UPB ndc DO
FOR j FROM i BY i TO UPB ndc DO ndc[ j ] +:= 1 OD
OD;
# show the numbers with prime divisor counts #
print( ( "Numbers up to ", whole( max number, 0 ), " with odd prime divisor counts:", newline ) );
INT p count := 0;
FOR i TO UPB ndc DO
INT divisor count = ndc[ i ];
IF ODD divisor count AND ndc[ divisor count ] = 2 THEN
print( ( whole( i, -8 ) ) );
IF ( p count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( newline ) );
max number := 100 000
OD
END</lang>
- Output:
Numbers up to 1000 with odd prime divisor counts:
4 9 16 25 49 64 81 121 169 289
361 529 625 729 841 961
Numbers up to 100000 with odd 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 65536 66049 69169 72361
73441 76729 78961 80089 83521 85849 94249 96721 97969
C++
<lang cpp>#include <cmath>
- include <cstdlib>
- include <iomanip>
- include <iostream>
int divisor_count(int n) {
int total = 1;
for (; (n & 1) == 0; n >>= 1)
++total;
for (int p = 3; p * p <= n; p += 2) {
int count = 1;
for (; n % p == 0; n /= p)
++count;
total *= count;
}
if (n > 1)
total *= 2;
return total;
}
bool is_prime(int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
int main(int argc, char** argv) {
int limit = 1000;
switch (argc) {
case 1:
break;
case 2:
limit = std::strtol(argv[1], nullptr, 10);
if (limit <= 0) {
std::cerr << "Invalid limit\n";
return EXIT_FAILURE;
}
break;
default:
std::cerr << "usage: " << argv[0] << " [limit]\n";
return EXIT_FAILURE;
}
int width = static_cast<int>(std::ceil(std::log10(limit)));
int count = 0;
for (int n = 1; n < limit; ++n) {
int divisors = divisor_count(n);
if (divisors != 2 && is_prime(divisors))
std::cout << std::setw(width) << n << (++count % 10 == 0 ? '\n' : ' ');
}
std::cout << "\nCount: " << count << '\n';
return EXIT_SUCCESS;
}</lang>
- Output:
Default input:
4 9 16 25 49 64 81 121 169 289 361 529 625 729 841 961 Count: 16
Stretch goal:
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: 79
Go
<lang go>package main
import (
"fmt" "math" "rcu"
)
func countDivisors(n int) int {
count := 0
i := 1
k := 1
if n%2 == 1 {
k = 2
}
for ; i <= int(math.Sqrt(float64(n))); i += k {
if n%i == 0 {
count++
j := n / i
if j != i {
count++
}
}
}
return count
}
func main() {
const limit = 1e5
var results []int
for i := 3; i < limit; i++ {
n := countDivisors(i)
if n > 2 && rcu.IsPrime(n) {
results = append(results, i)
}
}
climit := rcu.Commatize(limit)
fmt.Printf("Positive integers under %7s whose number of divisors is an odd prime:\n", climit)
under1000 := 0
for i, n := range results {
fmt.Printf("%7s", rcu.Commatize(n))
if (i+1)%10 == 0 {
fmt.Println()
}
if n < 1000 {
under1000++
}
}
fmt.Printf("\n\nFound %d such integers (%d under 1,000).\n", len(results), under1000)
}</lang>
- Output:
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 1,024 1,369 1,681 1,849
2,209 2,401 2,809 3,481 3,721 4,096 4,489 5,041 5,329 6,241
6,889 7,921 9,409 10,201 10,609 11,449 11,881 12,769 14,641 15,625
16,129 17,161 18,769 19,321 22,201 22,801 24,649 26,569 27,889 28,561
29,929 32,041 32,761 36,481 37,249 38,809 39,601 44,521 49,729 51,529
52,441 54,289 57,121 58,081 59,049 63,001 65,536 66,049 69,169 72,361
73,441 76,729 78,961 80,089 83,521 85,849 94,249 96,721 97,969
Found 79 such integers (16 under 1,000).
Julia
<lang julia>using Primes
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)))
</lang>
- Output:
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
Phix
with javascript_semantics function pd(integer n) n = length(factors(n,1)) return n!=2 and is_prime(n) end function for k=3 to 5 by 2 do integer n = power(10,k) sequence res = filter(tagset(n),pd) printf(1,"%d < %,d found: %V\n",{length(res),n,shorten(res,"",5)}) end for
- Output:
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}
REXX
Some optimization was added so as to bypass finding divisors for primes. <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*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*W: the maximum width of any column. */ title= ' positive integers N whose number of divisors is prime (and not equal to 2), ' ,
"where N < " commas(hi)
say ' index │'center(title, 1 + cols*(w+1) ) say '───────┼'center("" , 1 + cols*(w+1), '─') finds= 0; idx= 1; $=
do j=1 for hi-1 /*process positive integers in range. */
if !.j then iterate /*Is J prime? Then skip this number.*/
else do; n= nDivs(j) /*get number of divisors of composite J*/
if n==2 then iterate
if \!.n then iterate /*Number divisors prime? No, then skip*/
end
finds= finds + 1 /*bump the number of found numbers. */
$= $ right( commas(j), w) /*add a positive integer ──► $ list. */
if finds//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/ /* [↑] process a range of integers. */
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(finds) title exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ nDivs: procedure; parse arg x; d= 2; if x==1 then return 1 /*handle special case of 1*/
odd= x // 2 /* [↓] process EVEN or ODD ints. ___*/
do j=2+odd by 1+odd while j*j<x /*divide by all the integers up to √ x */
if x//j==0 then d= d + 2 /*÷? Add two divisors to the total. */
end /*j*/ /* [↑] % ≡ integer division. */
if j*j==x then return d + 1 /*Was X a square? Then add 1 to total.*/
return d /*return the total. */
/*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " semaphores. */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
do j=@.#+2 by 2 to hi-1 /*find odd primes from here on. */
parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</lang>
- output when using the default inputs:
index │ positive integers N whose number of divisors is prime (and not equal to 2), where N < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 4 9 16 25 49 64 81 121 169 289 11 │ 361 529 625 729 841 961 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 16 positive integers N whose number of divisors is prime (and not equal to 2), where N < 1,000
- output when using the input of: 100000
index │ positive integers N whose number of divisors is prime (and not equal to 2), where N < 100,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 4 9 16 25 49 64 81 121 169 289 11 │ 361 529 625 729 841 961 1,024 1,369 1,681 1,849 21 │ 2,209 2,401 2,809 3,481 3,721 4,096 4,489 5,041 5,329 6,241 31 │ 6,889 7,921 9,409 10,201 10,609 11,449 11,881 12,769 14,641 15,625 41 │ 16,129 17,161 18,769 19,321 22,201 22,801 24,649 26,569 27,889 28,561 51 │ 29,929 32,041 32,761 36,481 37,249 38,809 39,601 44,521 49,729 51,529 61 │ 52,441 54,289 57,121 58,081 59,049 63,001 65,536 66,049 69,169 72,361 71 │ 73,441 76,729 78,961 80,089 83,521 85,849 94,249 96,721 97,969 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 79 positive integers N whose number of divisors is prime (and not equal to 2), where N < 100,000
Ring
<lang ring> load "stdlib.ring" row = 0
see "working..." + nl see "Numbers which count of divisors is prime are:" + nl
for n = 1 to 1000
num = 0
for m = 1 to n
if n%m = 0
num++
ok
next
if isprime(num) and num != 2
see "" + n + " "
row++
if row%5 = 0
see nl
ok
ok
next
see nl + "Found " + row + " numbers" + nl see "done..." + nl </lang>
- Output:
working... Numbers which count of divisors is prime are: 4 9 16 25 49 64 81 121 169 289 361 529 625 729 841 961 Found 16 numbers done...
Wren
<lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt
var limit = 1e5 var results = [] for (i in 3...limit) {
var n = Int.divisors(i).count if (n > 2 && Int.isPrime(n)) results.add(i)
} Fmt.print("Positive integers under $,7d whose number of divisors is an odd prime:", limit) for (chunk in Lst.chunks(results, 10)) Fmt.print("$,7d", chunk) var under1000 = results.count { |r| r < 1000 } System.print("\nFound %(results.count) such integers (%(under1000) under 1,000).")</lang>
- Output:
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 1,024 1,369 1,681 1,849
2,209 2,401 2,809 3,481 3,721 4,096 4,489 5,041 5,329 6,241
6,889 7,921 9,409 10,201 10,609 11,449 11,881 12,769 14,641 15,625
16,129 17,161 18,769 19,321 22,201 22,801 24,649 26,569 27,889 28,561
29,929 32,041 32,761 36,481 37,249 38,809 39,601 44,521 49,729 51,529
52,441 54,289 57,121 58,081 59,049 63,001 65,536 66,049 69,169 72,361
73,441 76,729 78,961 80,089 83,521 85,849 94,249 96,721 97,969
Found 79 such integers (16 under 1,000).