没找到好的dup。这是一个复杂度为 O(sqrt(n)) 的解决方案。它取自https://www.geeksforgeeks.org/count-divisors-n-on13/
// function to count the divisors
int countDivisors(int n)
{
int cnt = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
// If divisors are equal,
// count only one
if (n / i == i)
cnt++;
else // Otherwise count both
cnt = cnt + 2;
}
}
return cnt;
}
在同一个站点上,有一个运行在 O(n^(1/3)) 中的站点稍微复杂一些。它适用于 C++,但只需添加#include <stdbool.h>
,它应该可以工作。
void SieveOfEratosthenes(int n, bool prime[],
bool primesquare[], int a[])
{
// Create a boolean array "prime[0..n]" and initialize all entries as
// true. A value in prime[i] will finally be false if i is Not a prime,
// else true.
for (int i = 2; i <= n; i++)
prime[i] = true;
// Create a boolean array "primesquare[0..n*n+1]" and initialize all
// entries it as false. A value in squareprime[i] will finally be true
// if i is square of prime, else false.
for (int i = 0; i <= (n * n + 1); i++)
primesquare[i] = false;
// 1 is not a prime number (Look it up if you doubt it)
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
int j = 0;
for (int p = 2; p <= n; p++) {
if (prime[p]) {
// Storing primes in an array
a[j] = p;
// Update value in primesquare[p*p], if p is prime.
primesquare[p * p] = true;
j++;
}
}
}
// Function to count divisors
int countDivisors(int n)
{
// If number is 1, then it will have only 1
// as a factor. So, total factors will be 1.
if (n == 1)
return 1;
bool prime[n + 1], primesquare[n * n + 1];
int a[n]; // for storing primes upto n
// Calling SieveOfEratosthenes to store prime factors of n and to store
// square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a);
// ans will contain total number of distinct divisors
int ans = 1;
// Loop for counting factors of n
for (int i = 0;; i++) {
// a[i] is not less than cube root n
if (a[i] * a[i] * a[i] > n)
break;
// Calculating power of a[i] in n.
int cnt = 1; // cnt is power of prime a[i] in n.
while (n % a[i] == 0) // if a[i] is a factor of n
{
n = n / a[i];
cnt = cnt + 1; // incrementing power
}
// Calculating number of divisors. If n = a^p * b^q then total
// divisors of n are (p+1)*(q+1)
ans = ans * cnt;
}
// if a[i] is greater than cube root of n
// First case
if (prime[n])
ans = ans * 2;
// Second case
else if (primesquare[n])
ans = ans * 3;
// Third casse
else if (n != 1)
ans = ans * 4;
return ans; // Total divisors
}
如果以上还不够,您应该研究某种动态规划。上述两种方法都是从头开始计算每个数字。但是,如果您要对多个数字执行此操作,则很有可能您可以使用以前数字中的信息。只是为了说明它是如何工作的,这是一个计算从 2 到 n 的所有素数的算法:
#include <stdbool.h>
#include <stdio.h>
#include <math.h>
// After running this function, prime[n] will be true iff n is a prime
void createPrimeArray(bool *prime, size_t size)
{
prime[0] = prime[1] = false;
for(size_t i=2; i<size; i++)
prime[i] = true;
for(size_t i=2; i<sqrt(size); i++) {
size_t j=i;
while(!prime[j])
j++;
for(size_t k=2*j; k<size; k+=j)
prime[k] = false;
}
}
int main(void)
{
bool prime[200];
createPrimeArray(prime, 200);
for(int i=0; i<200; i++) {
if(prime[i])
printf("%d ", i);
}
}
上述内容可能会进一步优化。它的目的是展示如何重用信息。在第二个 for 循环的第一次运行之后,createPrimeArray
我们将所有可被 2 整除的数字标记为非质数,因此我们不必再关心这些了。