欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

筛法求素数

程序员文章站 2024-03-15 12:57:47
...

筛法描述:

把 2 到 n 中所有的数列出来, 然后从 2 开始, 先划掉 n 内所有 2 的倍数, 然后每次从下一个剩下的数(必然是素数)开始,划掉其 n 内的所有倍数。最后剩下的数,就都是素数了。

思路:

  • 设置一个标志数组 is_prime, is_prime[i] 的值是 1 就表示 i 是素数,开始数组元素值全部为 1
  • 划掉 k 的倍数, 就是把 is_prime[2k], is_prime[3k] …… 标记为 0
  • 最后检查 is_prime 数组,如果is_prime[i] 值为 1 那么 i 就是素数

实现:

// 筛法求素数
#include <iostream>
#include <cstdio>
using namespace std;

const int max_size = 1000;
// 大数组定义在外面
char is_prime[max_size+1]; // 最终如果 is_prime 为 1,则表示 i 是素数

int main(void)
{
    int i, j;
    for (i=2; i<max_size+1; i++){   // 开始假设所有数都是素数
        is_prime[i] = 1;
    }
    
    for(i=2; i<max_size+1; i++){    // 每次将一个素数所有的倍数标记为非素数
        if (is_prime[i] == 1){  // 只标记素数的倍数
            for (j=2*i; j<max_size+1; j+=i){
                is_prime[j] = 0;    // 将素数 i 的倍数标记为非素数
            }
        }
    }
    
    for (i=2; i<max_size+1; i++){
        if (is_prime[i] == 1){
            cout << i << endl;
        }
    }
    return 0;
}

筛法是一种一空间换取时间的方法。