这段代码是如何计算一个数的除数的？

Question

http://www.spoj.com/problems/NDIV/

这是问题陈述。由于我是编程新手，这个特殊问题把我骗了，我在互联网上发现了这个特殊代码，当我尝试提交时得到了 AC。我想知道这段代码是如何工作的，因为我是从在线资源提交的，这本身对初学者来说是个坏主意。

#include <bits/stdc++.h>
using namespace std;
int check[32000];
int prime[10000];
void shieve()
{
    for(int i=3;i<=180;i+=2)
    {
        if(!check[i])
        {
            for(int j=i*i;j<=32000;j+=i)
                check[j]=1;
        }
    } 
    prime[0] = 2;
    int j=1;
    for(int i=3;i<=32000;i+=2)
    {
        if(!check[i]){
            prime[j++]=i;
        }
    } 
}
int main()
{ 
    shieve();
    int a,b,n,temp,total=1,res=0;
    scanf("%d%d%d",&a,&b,&n);
    int count=0,i,j,k;
    for(i=a;i<=b;i++)
    {
        temp=i;
        total=1;
        k=0;
        for(j=prime[k];j*j<=temp;j=prime[++k])
        {
            count=0;
            while(temp%j==0)
            {
                count++;
                temp/=j;
            }
            total *=count+1;
        }
        if(temp!=1)
            total*=2;
        if(total==n)
            res++;
    }
    printf("%d\n",res);
    return 0;
}

看起来代码在 eratosthenes 筛上有效，但有些事情我无法理解。

为什么数组"check"的极限是32000？
再次说明为什么数组素数的限制是 10000？
在 main 内部，j 的 for 循环内部发生的任何事情。

关于这种方法有太多的困惑，谁能解释一下整个算法是如何工作的。

Answer 1

设置数组的硬限制可能是因为问题需要这样？如果不是，那么只是错误的代码。
在内循环中，您正在计算素数的最大幂次方。为什么？参见第 3 点。
一个数n的因数个数可以这样计算：

令 n = (p1)^(n1) * (p2)^(n2) ... 其中 p1、p2 是素数，n1、n2 ... 是它们的指数。那么n的因子个数 = (n1 + 1)*(n2 + 1)...

因此，total *= count + 1 行基本上是 total = total * (count + 1)（其中 count 是除以原始数的素数的最大指数）计算素数的个数数.

是的，代码实现了埃拉托色尼筛法，用于将素数存储在 table。

(Edit 刚看到问题 - 您至少需要 10^4 boolean 个值来存储素数（您实际上不需要存储这些值，只是一个指示值是否为质数的标志。给出的条件是 0 <= b - a <= 10^4 ，因此从 a 开始循环到 b 并检查 bool 值存储在数组中以了解它们是否为质数。）

这段代码是如何计算一个数的除数的？

How is this code working for finding the number of divisors of a number?

c++

sieve-of-eratosthenes

factors