概念：

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

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

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

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

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

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1 ≤ n ≤ 100,
1 ≤ ai ≤ 2^31 − 1

输入样例：

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，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

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

数据范围

1 ≤ n ≤ 100,
2 ≤ ai ≤ 2×10^9

输入样例：

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= 1000010;

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 行，每行输出一个整数对的最大公约数。

数据范围

1 ≤ n ≤ 10^5，
1 ≤ ai,bi ≤ 2×10^9

输入样例：         

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