小编ala*_*ita的帖子

我必须计算超过2到100000的不同素因子的数量,有没有比我正在做的快速方法？即.2有1个不同的素因子2 10有2个不同的素因子(2,5)12有2个不同的素因子(2,3)我的代码: -

#include<stdio.h>
#include<math.h>
typedef unsigned long long ull;
char prime[100000]={0};
int P[10000],fact[100000],k;

void sieve()
{
    int i,j;
    P[k++]=2;
    for(i=3;i*i<1000;i+=2)    
    {
            if(!prime[i])
            {
                    P[k++]=i;
                    for(j=i*i;j<100000;j+=i+i)    
                            prime[j] = 1;
            }
    }
    for(i=1001;i<100000;i+=2)    
            if(!prime[i])
                    P[k++]=i;
}

int calc_fact() {
  int root,i,count,j;
  fact[1]=fact[2]=fact[3]=1;
  for(i=4;i<=100000;i++) {
     count=0;
     root=i/2+1;
     for(j=0;P[j]<=root;j++) {
        if(i%P[j]==0)count++;
     }
     if(count==0) fact[i]=1;
     else fact[i]=count;
  }
 return 0;
}
int main(){
 int i;
 sieve();
 calc_fact(); 
 for(i=1;i<10000;i++) printf("%d  ,",fact[i]);
 return 0;
}