质数
质数的定义
在大于 1 的整数中，只包含 1 和自己本身两个约数的数，被称为质数（素数）
质数的判定----试除法O(sqrt(n))
866. 试除法判定质数
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100,
1≤ai≤231−1
输入样例：
2
2
6
输出样例：
Yes
No
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n;
bool is_prime(int x)
{
if(x < 2) return false;
for(int i = 2; i < sqrt(x); i ++ ){
if(x % i == 0) return false;
}
return true;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++ ){
int x;
cin >> x;
if(is_prime(x)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
分解质因数----试除法O(sqrt(n))
867. 分解质因数
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例：
2
6
8
输出样例：
2 1
3 1
2 3
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n;
void check(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;
cout << endl;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++ ){
int x;
cin >> x;
check(x);
}
return 0;
}
筛质数
868. 筛质数
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例：
8
输出样例：
4
基本思想
对于 2 3 4 5 6 7 8 9 10 11 12 … P
我们首先将 2 的倍数都筛掉
2 3 5 7 9 11 … P
然后再将 3 的倍数都筛掉
2 3 5 7 11 … P
…
…
最后，对于 P 来说，将 P 的倍数都筛掉，对于 P 之前的数来说，都已经被前面的数筛过了，也就是说， P 一定是质数
朴素法O(nlogn)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n;
bool st[N];
int prime[N], cnt;
void check(int x)
{
for(int i = 2; i <= n; i ++ ){
if(!st[i]){
prime[cnt ++ ] = i;
}
for(int j = i; j <= n; j += i){
st[j] = true;
}
}
}
int main()
{
cin >> n;
check(n);
cout << cnt << endl;
return 0;
}
埃式筛法O(nloglogn)
由朴素法优化而来，对于 P 来说，前面的合数，会在前面筛的时候，被一些质数筛掉，因此，我们就只需要将质数的倍数筛掉即可
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n;
bool st[N];
int prime[N], cnt;
void check(int x)
{
for(int i = 2; i <= n; i ++ ){
if(!st[i]){
prime[cnt ++ ] = i;
for(int j = i; j <= n; j += i){
st[j] = true;
}
}
}
}
int main()
{
cin >> n;
check(n);
cout << cnt << endl;
return 0;
}
线性筛法O(n)
void get_primes(){
//外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就
//没啥意义了
st[primes[j]*i]=true;//用最小质因子去筛合数
//1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的
//最小质因子,所以primes[j]*i的最小质因子就是primes[j];
//2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
//prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小
//质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
//退出循环，避免之后重复进行筛选。
if(i%primes[j]==0) break;
}
}
}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n;
bool st[N];
int prime[N], cnt;
void check(int x)
{
for(int i = 2; i <= n; i ++ ){
if(!st[i]){
prime[cnt ++ ] = i;
}
for(int j = 0; prime[j] <= n / i; j ++ ){
st[prime[j] * i] = true;
if(j % prime[j] == 0) break;
}
}
}
int main()
{
cin >> n;
check(n);
cout << cnt << endl;
return 0;
}