质数——acwing

素数几种方法（区间筛）-CSDN博客

之前做的笔记👆👆👆

题目一：试除法判定质数

866. 试除法判定质数 - AcWing题库

代码 

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

bool isprime(int x) {
    if(x == 1) return false;
    for(int i = 2; i<=x/i; i ++) { // i*i可能越界，开方函数太慢
        if(x%i==0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    while(n --) {
        int x;
        cin >> x;
        if(isprime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

题目二：分解质因数

867. 分解质因数 - AcWing题库

 代码(TLE )

11个数据过了7个

从质因数从2开始，只要x能被除就不断除，可以被除的条件是，x%i==0； 还有个条件是x!=1,是因为x除到最后一定为1，也是循环结束条件。

分析题目会发现：

只要x本身是质数那么只会被本身除掉。

如果不是质数，例如8，22，16，9等等，都会被他们的质因数不断除。例如27.

27/3 = 9， 9/3 = 3， 3/3 = 1；

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

void solve(int x) {
    for(int i = 2; x!=1 && i <= x; i ++) {
        int cnt = 0;
        while(x%i==0) {
            cnt ++;
            x /= i;
        }
        if(cnt) {
            cout << i << " " << cnt << endl;
        }
    }
}

int main() {
    int n; cin >> n;
    while(n --) {
        int x; cin >> x;
        solve(x);
        cout << endl;
    }
    return 0;
}

代码2

x除以质因子，除到后面会发现，从例子可以看出来，他只会不断除以一个质因子，然后剩下一个质因子。那个质因子是大于sqrt(x)的也是唯一 一个。

28 /2 = 14， 14/2 = 7    => 7*7=49>28,明显最后一个质因子是大于的。

而质数本身就是最大的那个质因子，也就是上面除剩下的。其实是因为前面跳过了sqrt前面的质因子环节

所以只要循环找sqrt前面的质因子，除剩下单独处理。

或者说：

只会有一个质因子是超过sqrt(x)的，也就是要单独处理。

其他就不断处理[2,sqrt(x)]的质因子。

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

void solve(int x) {
    // 遍历，不断找质因子 遍历【2，sqrt(x)]
    for(int i = 2; i <= x/i; i ++) {
        if(x%i==0) {
            int cnt = 0;
            while(x%i==0) {
                x /= i;
                cnt ++;
            }
            
            cout << i << " " << cnt << endl;
        }
    }
    // 剩下一个质数
    if(x>1) cout << x << " " << 1 << endl;
}

int main() {
    int n; cin >> n;
    while(n --) {
        int x; cin >> x;
        solve(x);
        puts("");
    }
    return 0;
}

题目三：筛质数

868. 筛质数 - AcWing题库

代码 (欧拉筛）

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

const int N = 1e6+10;
int prime[N], cnt; // 存素数
bool vis[N]; // 标记素数
// 欧拉筛

void solve(int n) {
    
    for(int i = 2; i <= n; i ++) {
        if(vis[i]) prime[cnt++] = i;
        for(int j = 0; j < cnt && i*prime[j]<=n; j ++) {
            vis[i*prime[j]] = false;
            if(i%prime[j]==0) break;
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    memset(vis,true,sizeof vis);
    solve(n);
    
    cout << cnt << endl;
    
    return 0;
}

代码2（埃氏筛）

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

const int N = 1e6+10;
int prime[N], cnt;
bool vis[N];

// 埃氏筛，用质因子来筛
void solve(int n) {
    for(int i = 2; i <= n/i; i ++) {
        if(vis[i]) {
            for(int j = 2*i; j <= n; j += i) {
                vis[j] = false;
            }
        }
    }
    for(int i = 2; i <= n; i ++) {
        if(vis[i]) prime[cnt++] = i;
    }
}

int main() {
    int n;
    cin >> n;
    
    memset(vis,true,sizeof vis);
    solve(n);
    
    cout << cnt << endl;
    return 0;
}

原文地址：https://blog.csdn.net/2401_87338545/article/details/144121510

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！