質數、找質因數(埃氏篩)

from 2024 IONC

質數定義

對於一個大於 \(1\) 的整數，如果其因數只有自己和 \(1\)，則稱這個數是質數，否則稱為合數。在此定義中 \(1\) 既不是質數也不是合數。

判斷質數

時間複雜度為 \(O(\sqrt{n})\)

#include<bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(0);cin.tie(0);
#define all(x) x.begin(),x.end()

string isp(int n){
    if(n<2)return "非質數\n";
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return "非質數\n";
        }
    }
    return "質數\n";
}

int main(){io
    // stringstream cin("13 14");
    int n;

    while(cin>>n){
        cout<<isp(n);
    }
}

埃式篩法

複雜度：O ( n log ⁡ ( log ⁡ n ) )

順便找質因數的解

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define io ios::sync_with_stdio(0);cin.tie(0);

vector<vector<int>> p(int n) {
    vector<vector<int>> v(n + 1);
    for (int i = 2; i <= n; ++i) { //對於每個數
        if (v[i].size()==0) {
            for (int j = i; j <= n; j += i) { // 找倍數
                v[j].push_back(i);
            }
        }
    }
    return v;
}


int main(){io
    //stringstream cin("10");

    int n;
    cin>>n;
    vector<vector<int>> v=p(n);

    for(int i=1;i<=n;i++){
        cout<<i<<":";
        for(int i:v[i]){
            cout<<i<<" ";
        }
        cout<<nn;
    }

}

線性解，但是就沒有找質因數

複雜度：O(n)

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define io ios::sync_with_stdio(0);cin.tie(0);
#define int long long


vector<int> p(const int M) {
    vector<int> primes, divider(M+1, 0); //divider存最小質因數
    for (int n = 2; n <= M; n++) {  //對於所有的數字
        //cout<<n<<": "<<nn;
        if (divider[n] == 0) {  // 如果是質數
            primes.emplace_back(n), divider[n] = n;// prime記錄所有質數
        }
        for (int j = 0; primes[j] * n <= M; ++j) { // 對於小於n的所有質數，將n乘以質數得到新數
            //cout<<primes[j]<<" "<<primes[j] * n<<nn;
            divider[primes[j] * n] = primes[j]; //將n的最小因數給n
            if (n % primes[j] == 0) break; //可以整除
        } 
    }
    return primes;
}



vector<int> sieve(int N) { //第二種
	vector<bool> is_prime(N + 1, true);
	is_prime[0] = is_prime[1] = false;
	vector<int> primes;
	for(int i = 2; i <= N; i++) {
		if(is_prime[i]) {
			primes.push_back(i);
		}
		for(auto j : primes) {
			if(i * j > N) {
				break;
			}
			is_prime[i * j] = false;
			if(i % j == 0) {
				break;
			}
		}
	}
	return primes;
}

signed main(){io
    int n=19;
    vector<int> v=p(n);
    for(int i:v){
        cout<<i<<nn;
    }
}

米勒-拉賓質數判定法

https://blog.csdn.net/Emm_Titan/article/details/121304016

例題

a007. 判斷質數

大師題解

先找出 \(\sqrt{2147483647}\) 以內的質數。對於每個數字 \(n\)，檢查是否有質數能整除即可。
因為所有和數一定是由質數組成

線性篩

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define io ios::sync_with_stdio(0);cin.tie(0);



vector<int> p(const int M) {
    vector<int> primes, divider(M+1, 0); //divider存最小質因數
    for (int n = 2; n <= M; n++) {  //對於所有的數字
        //cout<<n<<": "<<nn;
        if (divider[n] == 0) {  // 如果是質數
            primes.emplace_back(n), divider[n] = n;// prime記錄所有質數
        }
        for (int j = 0; primes[j] * n <= M; ++j) { // 對於小於n的所有質數，將n乘以質數得到新數
            //cout<<primes[j]<<" "<<primes[j] * n<<nn;
            divider[primes[j] * n] = primes[j]; //將n的最小因數給n
            if (n % primes[j] == 0) break; //可以整除
        } 
    }
    return primes;
}


signed main(){io

    //istringstream cin("13 14");

    int n=sqrt(2147483647);
    vector<int> v=p(n);
    
    int k;
    while(cin>>k){
        int is=1;
        for(int i:v){
            if(k%i==0){
                if(i != k) {
					is = 0;
				}
                break;
            }
        }
        if(is){
            cout<<"質數\n";
        }
        else{
            cout<<"非質數\n";
        }
    }

}

expandcollapse