数论-质数基础
1.素数
素数又称为质数，是指除了1和本身之外，不能被其他数整除的一类数。即对给定的正整数n,如果对任意的正整数a(1<a<n)，都有n%a!=0成立，那么称n是素数;否则，如果存在a(1<a<n),使得n%a==0，那么称n为合数。应特别注意的是，1既不是素数，也不是合数。
2.素数的判断
试除法
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;}
for()循环中有三种写法(1). i * i<=n 这样写当n接近int型变量的范围上限时会导致i * i溢出。
(2) i<=sqrt(n) 每次循环都要计算sqrt(n) ,浪费时间。
(3) i<=n/i 这种写法的效率高而且安全。
3.试除法分解质因数
//试除法分解质因数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; //大于sqrt(n)的质因数只有一个，n本身cout << endl;}
4.筛法求1-n之间的素数
(1).最普通的筛法 O(nlogn)
int primes[N], cnt;// primes[]存储所有素数bool st[N]; // st[x]存储x是否被筛掉 void get_primes(){for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;//把素数存起来for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数st[j]=true;}}}
(2).诶氏筛法 O(nloglogn)
int primes[N], cnt;// primes[]存储所有素数bool st[N]; // st[x]存储x是否被筛掉 void get_primes(){for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；}}}
(3).线性筛法 O(n)
用一个合数的最小质因子去筛这个合数
//线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了//算法核心：x仅会被其最小质因子筛去int primes[N], cnt;// primes[]存储所有素数bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int x) {for(int i = 2; i <= x; i++) {if(!st[i]) prime[cnt++] = i;for(int j = 0; prime[j] <= x / i; j++) {//对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉st[prime[j]*i] = true;if(i % prime[j] == 0) break;/*1.i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子*/}}}
5.题目练习
(1)AcWing 866. 试除法判定质数
给定n个正整数ai，判定每个数是否是质数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
共n行，其中第 i 行输出第 i 个正整数ai是否为质数，是则输出“Yes”，否则输出“No”。
数据范围
1≤n≤100,
1≤ai≤2∗109
输入样例：
2
2
6
输出样例：
Yes
No
代码
#include<iostream>#include<cstdio>using namespace std;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(){int n;cin >> n;while (n--){int x;cin >> x;if (is_prime(x)){cout << "Yes" << endl;}else{cout << "No" << endl;}}return 0;}
(2)AcWing-867. 分解质因数
给定n个正整数ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
对于每个正整数ai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
1≤ai≤2∗109
输入样例：
2
6
8
输出样例：
2 1
3 1
2 3
代码
//试除法分解质因数#include<iostream>#include<cstdio>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; //大于sqrt(n)的质因数只有一个，n本身cout << endl;}int main(){int n;cin >> n;while (n--){int x;cin >> x;divide(x);}return 0;}
(3)AcWing-868. 筛质数
给定一个正整数n，请你求出1~n中质数的个数。
输入格式
共一行，包含整数n。
输出格式
共一行，包含一个整数，表示1~n中质数的个数。
数据范围
1≤n≤106
输入样例：
8
输出样例：
4
代码
#include<iostream>#include<cstdio>using namespace std;const int maxn = 1e6 + 10;int primes[maxn],cnt; //存储所有素数bool st[maxn]; //st[x]存储x是否被筛掉//朴素筛法//void get_primes(int n)//{//for (int i = 2; i <= n; i++)//{//if (!st[i]) primes[cnt++] = i;//for (int j = i + i; j <= n; j += i)//{//st[j] = 1;//}//}//}//线性筛法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] = 1;if (i%primes[j] == 0) break;}}}int main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;}
