质数的判断

• 0和1既不是质数，也不是合数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


bool isPrime(int x){
    if(x < 2) return false;
    //枚举到根号x
    for (int i = 2; i <= x / i; i ++ ){
        if(x % i == 0) return false;
    }
    return true;
}

//第二种O(NloglogN)
//埃氏筛法
int st[100000];
void primes(int x){
    memset(st, 0, sizeof st);
    for (int i = 2; i <= x; i ++ ){
        //被标记过了，不是质数
        if(st[i] == 1)continue;
        //i是质数
        cout << i << endl;
        //把i的倍数全部筛选掉
        //为避免过多的重复筛选，小于i的平方的数在i之前被筛选过了，所以j从i开始
        for (int j = i; j <= x / i; j ++ ) st[i*j] = 1;
    }
}

//第3种O(n)
//线性筛法
//暂时没看懂
int v[100000], p[100000];
void primes2(int x){
    memset(st, 0, sizeof st);
    int m = 0;
    for (int i = 2; i <= x; i ++ ){
        if(v[i] == 0){
            v[i] = i;
            p[++m] = i;
        }
        for (int j = 1; j <= m; j ++ ){
            if(p[j] > v[i] || p[j] > x / i) break;
            v[i * p[j]] = p[j];
        }
    }
    for (int i = 1; i <= m; i ++ ) cout << p[i] << endl;
}

int main()
{
    int x = 56;
    // cout << isPrime(x);
    // primes(x);
    primes2(x);

}