质因子筛法

今天在求   1- 200000 内所有的数的质子的时候想到一个优美的算法.  它利用到筛法的特性

代码:

void solve(){
    
    memset(num,0,sizeof(num));
    memset(hs,0,sizeof(hs));
    for(int i = 2 ;i <= 200000;i ++)
    {
       if(hs[i] == 0 )
       {
           int k = i;
           while(k <= 200000)
           {
              num[k] ++ ; 
              prime[k][num[k]] = i ; 
              hs[k] = 1; 
              k += i ;
           }
       }
     
    }
}