质数

质数

定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。

（1）质数的判定——试除法

时间复杂度：O((sqrt{n}))

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

（2）分解质因数——试除法

n中最多只包含一个大于 (sqrt{n}) 的质因子。

时间复杂度：O((sqrt{n}))

http://acm.hdu.edu.cn/showproblem.php?pid=1164

题意：连续输入一个大于1的整数n，分解质因数。

#include <bits/stdc++.h>
using namespace std;

const char nl = '
';

vector<int> divide(int n){
    vector<int> ret;
    for (int i = 2; i <= n / i; ++i){
        if (n % i == 0){    // i一定是质数
            while (n % i == 0){
                ret.push_back(i);
                n /= i;
            }
        }
    }
    if (n > 1) ret.push_back(n);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
    int n;
    while (cin >> n){
        auto ret = divide(n);
        cout << ret[0];
        int m = ret.size();
        for (int i = 1; i < m; ++i){
            cout << "*" << ret[i];
        }
        cout << nl;
    }
    return 0;
}

（3）埃式筛法

1~n中有 (frac{n}{ln(n)}) 个质数。

时间复杂度：O(n(log)(log)n)

#include <bits/stdc++.h>
using namespace std;

const char nl = '
';
const int N = 1e8 + 5;

int tot = 0;
int primes[N];
bool st[N];

void get_primes(int n){
    for (int i = 2; i <= n; ++i){
        if (!st[i]){
            primes[tot++] = i;
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    get_primes(n);
    int k;
    while (m--){
        cin >> k;
        cout << primes[k - 1] << nl;
    }
    return 0;
}

（4）线性筛法

n只会被最小质因子筛掉。

时间复杂度：O(n)

https://www.luogu.com.cn/problem/P3383

题意：给定一个范围n，有m个询问，每次输出第k个素数。

#include <bits/stdc++.h>
using namespace std;

const char nl = '
';
const int N = 1e8 + 5;

int tot = 0;
int primes[N];
bool st[N];

void get_primes(int n){
    for (int i = 2; i <= n; ++i){
        if (!st[i]) primes[tot++] = i;
        for (int j = 0; primes[j] <= n / i; ++j){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    get_primes(n);
    int k;
    while (m--){
        cin >> k;
        cout << primes[k - 1] << nl;
    }
    return 0;
}