素数筛选与最大质因子

    这两种模板其实大同小异，所以写在一起了。

    素数筛选：筛选1~MAX之间的素数，prime[i]的值为1表示i为素数，值为0则表示不是素数，代码如下：

int prime[MAX+10]; void init(){ memset(prime,0,sizeof(prime)); prime[1]=1; for(int i=2;i<MAX;i++){ if(prime[i]==1) continue; if(i>MAX/i) continue;//防止i*i超出long long而爆掉 for(int j=i*i;j<MAX;j+=i){ prime[j]=1; } } }       最大质因子：求出2~MAX之间某个数的最大质因子，prime[i]的值表示i的最大质因子，上代码：

int prime[MAX+10]; void init(){ memset(prime,0,sizeof(prime)); for(int i=2;i<MAX;i++){ if(prime[i]！=0) continue; for(int j=i;j<MAX;j+=i){ prime[j]=i; } } }