int n , a[100] , p[100];
void prime2(){
memset(a , 0 , n * sizeof(a[0])) ; //初始都为素数
int num = 0 , i , j ;
for( i =2 ; i <= n ; i++){
if(!a[i]) p[num++] = i ; // 质数表p[]
for(j = 0 ; j<num && i * p[j] <= n ; j++){
a[i * p[j]] = 1 ; // 筛以 i 为最大因子 的合数
if(!(i % p[j])) break ; // 找到i 的最小素因子 ， 终止
}
}
}
结论：
1： 对于每一个数i，乘上 小于等于i的最小素因数p 的素数，就得到以i为最大因数的合数 T = i * p。
2: 设有一个数t，只要将所有以比t小的数i为最大因数的合数筛去，那么比t小的数里剩下的就只有素数了。
原文：http://www.cnblogs.com/zn505119020/p/3784106.html