保研机试训练Day-16

数论

质数

试除法判定质数给定 n 个正整数，判定每个数是否是质数。

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

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

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        if(is_prime(x)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

分解质因数

给定 n 个正整数，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

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

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
void divide(int n){
    for(int i = 2;i <= n / i;i++){
        if(n % i == 0){
           int s=0;
           while(n % i == 0){
               n /= i;
               s++;
           }
           printf("%d %d\n",i,s);
        }
    }
  
    if(n > 1) printf("%d %d\n",n,1);
    puts("");
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        divide(x);
    }
    return 0;
}

筛质数

给定一个正整数 n，请你求出 1∼n 中质数的个数。

朴素筛法O(nlogn)：

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

const int N = 1000010;

int primes[N],cnt;
bool st[N];

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

int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d",cnt);
    return 0;
}

埃氏筛法 O(nloglogn)：

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

const int N = 1000010;

int primes[N],cnt;
bool st[N];

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

int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d",cnt);
    return 0;
}

线性筛法 O(n)：

核心是n只会被他的最小质因子筛掉

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

const int N = 1000010;

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;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d",cnt);
    return 0;
}

数论

数论

质数

分解质因数

筛质数

朴素筛法O(nlogn)：

埃氏筛法 O(nloglogn)：

线性筛法 O(n)：

CATALOG

FEATURED TAGS