素数快速求法_素数 加速计算

素数指的是只能被1和自身整除的的数。那么如何求解出N以内的所有素数呢？

1、暴力解决 遍历两次

2、优化暴力 内层遍历只需遍历到N的开方   因为一个合数能被整除a*b = N，那么a和b必然有一个是小于N的开方的。所以要是合数的话，遍历到N开方前就会被除开，证明为合数。

3、以上还是不够快，所以使用筛选法，即2的倍数，3的倍数.....都要不是素数，直接删除

  1 #include <apue.h>
  2 
  3 #define MAX   100
  4 
  5 int main(int ac, char **av)
  6 {
  7     int flag[MAX];
  8     int i = 0;
  9     int j = 0;
 10     int count = 0;
 11 
 12     for(i = 0; i < MAX; i++){
 13         flag[i] = 1;
 14     }
 15 
 16     for(i = 2; i * i <= MAX; i++){
 17         if(flag[i]){
 18             for(j = 2 * i; j < MAX; j++){
 19                 if(j % i == 0){
 20                     flag[j] = 0;
 21                 }
 22             }
 23         }
 24     }
 25 

 26     for(i = 2; i < MAX; i++){
 27         if(flag[i]){
 28             printf("%4d ",i);
 29             count++;
 30 
 31             if(count % 5 == 0)
 32                 printf("\n");
 33         }
 34     }
 35     return 0;
 36 }

/* 1.对于一亿的数据量，应该在堆中申请；
* 2.为了提高程序效率将cout改为printf；
* 3.判断是否是倍数时，应将求摩运算改为加法
*/
const int length = 100000000;
bool *flag = new bool[length];


for (int i = 2; i < length; i++) {
for (int j = i + i; j < length; j += i) {
flag[j]= 1;
}
}


for (int i = 2; i < length; i++) {
if (flag[i] == 0) {
printf("%d ", i);
}
}

printf("\n");
    
delete []flag;

还有很多其他比较好的方法，素数密度法，Miller-Rabin随机素数测试法等，不同方法有不同的应用场景，有兴趣的话，可以在网上查查。