概念：

（1）质数（素数）：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

（2）质因数：指能整除给定正整数的质数。

（3）最大公约数（共因数）：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

此外：除了1之外，一个数的最小因数一定是质数 

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

给定 n 个正整数 ai，判定每个数是否是质数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围

输入样例：

2 2 6 

输出样例：

Yes No

AC代码：

#include <iostream> #include <algorithm> using namespace std; bool is_prime(int x) { if (x < 2) return false; //1既不是质数也不是合数 for (int i = 2; i <= x / i; i ++ ) //i到 <= sqrt(n) if (x % i == 0) //试除法 return false; return true; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; if (is_prime(x)) puts("Yes"); else puts("No"); } return 0; }

二、AcWing 867. 分解质因数 - AcWing       

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

输入样例：

2 6 8 

输出样例：

2 1 3 1 2 3

AC代码：

#include <iostream> using namespace std; void divide(int x) { for(int i = 2; i <= x / i; i ++ ) { //这里的i一定为x的质因子 //x%i==0 ==> i为x的因子 //若i非质数,则它的因子一定在[2,sqrt(i)]内 ==> 轮到i去试除x的时候,它的因子已经被除完了 ==> i必为质数 if(x % i ==0) { int s = 0; while(x % i == 0) { x /= i; s ++; } printf("%d %d\n", i, s); } } //若此时x>1,则代表x为质数,质数只能分解成它本身的1次方 if (x > 1) printf("%d %d\n", x, 1); puts(""); } int main() { int n; scanf("%d", &n); while(n -- ) { int x; scanf("%d", &x); divide(x); } return 0; }

三、 868. 筛质数 - AcWing题库

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n中质数的个数。

数据范围

1 ≤ n ≤ 10^6

输入样例：

8 

输出样例：

4

AC代码：
 第一种：最朴实的筛法O(nlogn)

#include <iostream> #include <algorithm> using namespace std; const int N= ; int primes[N], cnt; bool st[N]; //初始值为false 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]=true; //质数为false，筛选掉的合数为true } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; } 

第二种：埃氏筛法 O(nloglogn) 

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]=true;//可以用质数就把所有的合数都筛掉； } } }

第三种：线性筛法 O(n)        

核心：n只会被其最小质因子筛掉 

void get_primes(int n){ //外层从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， //遍历primes数组中的质数，直到质数乘以当前数i大于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; //primes[j]一定是i的最小质因子 } } }

四、872. 最大公约数 - AcWing题库

给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数对 ai,bi。

输出格式

输出共 n 行，每行输出一个整数对的最大公约数。

数据范围

输入样例：         

2 3 6 4 6 

输出样例：

3 2

 

AC代码：

#include <iostream> int get(int a, int b) { return b ? get(b, a % b) : a; } int main () { int n; scanf ("%d", &n); while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", get(a, b)); } return 0; }

 此外，可以接用STL中的欧几里得函数

#include<iostream> #include <algorithm> using namespace std; int n,a,b; int main() { cin >> n; while(n--){ cin >> a >> b; cout << __gcd(a,b) << endl;//调用STL函数 } return 0; }

2024/2/27