素数筛法(sieve of primer number)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**************************************************************** 
 * Description: C++ implementation of  Sieve of Erotoshenes  O(nloglogn)
 * Author: Alex Li
 * Date: 2023-06-21 12:35:06
 * LastEditTime: 2023-07-09 20:10:33
****************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
 
const int maxn = 1000000;
bool isPrimer[maxn];    // i是合数isPrimer为1，i是素数，isPrimer为0
 
void sieve(long long n){
    int m = sqrt(n);
    memset(isPrimer, 0, sizeof(isPrimer));//初始化数组
    isPrimer[2] = 0;
/*
从i*i开始筛选，小于i的数在之前的循环已经筛过，比如6是在i=2时候筛过了，所以j=3时就从3*3开始。
另外，由于i筛选的时候可能会重复前面已经筛过的，比如18，就是在i=2和3时，都筛一遍。
*/
    for (long long i = 2; i <= m; i ++) {
        if(!isPrimer[i])
            for (long long j = i * i; j <= n; j += i)
                isPrimer[j] = 1;
        if(i * i > n)
            break;
    }
}
 
int main(){
    long long n;
    cout << "input a number: ";
    cin >> n;
    sieve(n);
    cout<<"list of prime numbers less then n: ";
    for (long long i = 2; i < n; i++)
    if(isPrimer[i]==0)cout<<i<<' ';
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**************************************************************** 
 * Description: C++ implementation of  linear sieve primer number  O(n)
 * Author: Alex Li
 * Date: 2023-06-21 20:39:52
 * LastEditTime: 2023-06-21 22:31:04
****************************************************************/

#include <iostream>
using namespace std;
const int MAXN=1000000;
int visited[MAXN],prime[MAXN]; //visited[]是标识，visited[i]=1说明i是合数，visited[i]=0说明是质数，prime[i]是存质数

int main(){
    int n,count=0; //n是待求数，count是质数个数。
    cin>>n;
    for (int i =2; i <=n; i++){ //i从2开始找
     //visited[i]如果=0，则说明i是质数，放到pirme[i]数组里，count加1，visited[i]因为是全局数组，默认初始值是0 
        if(!visited[i]) {  
            prime[count]=i;
            count++;
        }
        //从最小的质数开始枚举
        for (int j = 0; j<count&&prime[j]*i<=n; j++){
            int k=prime[j];
            visited[i*k]=1;//i乘以小于i的质数，标识出合数
            //如果i是质数，当k=i时，退出
            //如果i是合数，当k等于i最小质因子的时候退出。
            if(i%k==0)break;
        }
    }
    for (int i = 0; i <count; i++)cout<<prime[i]<<' ';
return 0;

}