【AcWing】866~868. 质数

#include<iostream>
#include<math.h>
using namespace std;

int n;

bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x / i;i++){
        if(x % i == 0) return false;
    }
    return true;
}
int main(){
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        if(is_prime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;

void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            int s=0;
            while(x%i==0){
                x/=i;
                s++;
            }
            cout<<i<<" "<<s<<endl;
        }
    }
    if(x>1) cout<<x<<" "<<1<<endl;//单独处理大于根号n的质因子
    cout<<endl;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        divide(x);
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e6 + 10;

int n;
int primes[N],cnt;//存质数，质数个数
bool st[N];//这个数是否被筛选过

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){//没被筛过，说明是质数
            primes[cnt++]=i;
        }
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;//从小到大遍历的primes，每个数用最小的质因子筛去
            //在质数3加入的时候，i不会再等于2，所以不会重复删除6,2的3倍==3的2倍，每个质数删去的倍数只会>=自己的值
            if(i%primes[j]==0) break;//i是质数或合数，成立则primes是当前数的最小质因子
        }
    }
}

int main(){
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}