质数——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;
}