一、定义
若一个正整数无法被除1和它自身以外的自然数整除，则该数为质数（或素数），否则该数为合数 。
1既不是质数也不是合数 。
由定义可得质数的一个性质：只有1和它本身两个因数 。
补充：对于一个足够大的整数N，不超过N的质数大约有N/㏑N个 。即每㏑N个数中有1个质数 。
二、判定质数
根据定义：素数就是一个数除了1 和他本身没有其他因数的数叫做质数 。
于是我们对于一个N,可以可以从2枚举到N?1，从而判断这个数是不是质数 。
bool Is_prime(int n){if(n==1) return false;if(n==2) return true；for(int i=2;i
时间复杂度O(n);
对于上述程序显然不能满足我们的需求，如N较大时，这样的程序肯定容易超时，要想办法优化以上程序 。
优化
我们不难发现N的因数是成对出现的，所以对于任何一个整数N，我们只需要从1枚举到sqrt(N)就可以了 。
于是代码如下：
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;}
时间复杂度o(sqrt(n))
ps.关于i1，说明这就是大于sqrt(n)的唯一质因子，输出即可 。
试除法
我们可以扫描2~sqrt(N)之间的每一个整数d，若d能整除N，则从N中除掉所有的因子d，同时累计除去的d的个数 。
因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了，所以在上述过程中能整除N的一定是质数，最终就得到了质因数分解的结果，易知时间复杂度为O(sqrt(N)) 。
特别的，若N每有被任何2~sqrt(N)的数整除，则N是质数，无需分解 。
时间复杂度： o(n) --> o(sqrt(n))
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;}//特判, 如果不是1那么就是那个较大的质因子.//最多只有一个大于sqrt(n)的质因子.if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;}
经典例题
867. 分解质因数
给定n个正整数ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数 。
输入格式
第一行包含整数n 。
接下来n行，每行包含一个正整数ai 。
输出格式
对于每个正整数ai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行 。
每个正整数的质因数全部输出完毕后，输出一个空行 。
数据范围
1≤n≤100,
1≤ai≤2?109
输入样例：
268
输出样例：
2 13 12 3
#include #include 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;cout << endl;}int main(){int n;cin >> n;while (n -- ){int x;cin >> x;divide(x);}return 0;}
四、筛质数
868. 筛质数
给定一个正整数n，请你求出1~n中质数的个数 。
输入格式
共一行，包含整数n 。
输出格式
共一行，包含一个整数，表示1~n中质数的个数 。
数据范围
1≤n≤106
输入样例：
8