C语言--质数算法和最大公约数算法

1.在C语言中，判断质数的常见算法有以下几种：

1. 试除法（暴力算法）：从2开始依次除以每个小于该数的自然数，如果有余数为0的，则该数不是质数。

2. 优化试除法：只需要测试小于等于该数平方根的自然数，因为如果大于该数平方根的除数能整除该数，那么小于该数平方根的除数一定也能整除该数。

3. 埃拉托色尼筛法：从2开始，将数字的倍数都标记为合数，就可以找到所有的质数。

4. 米勒-拉宾素性检验：依靠不同的随机数，可以判断质数是否为合数，准确率高。

5. 线性筛法：从小到大依次筛选质数，并标记其倍数为合数。

6. 试除法（暴力算法）：

7. 素性检验

1.1.试除法（暴力算法）：

#include <stdio.h>

int isPrime(int n) 
{
    for (int i = 2; i < n; i++) 
    {
        if (n % i == 0) 
        {
            return 0;   // 不是质数
        }
    }
    return 1;   // 是质数
}

int main() 
{
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if (isPrime(n)) {
        printf("%d是质数\n", n);
    } else {
        printf("%d不是质数\n", n);
    }
    return 0;
}

1.2.优化试除法：

#include <stdio.h>
#include <math.h>

int isPrime(int n) 
{
    for (int i = 2; i <= sqrt(n); i++) 
    {
        if (n % i == 0) 
        {
            return 0;   // 不是质数
        }
    }
    return 1;   // 是质数
}

int main() 
{
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if (isPrime(n)) {
        printf("%d是质数\n", n);
    } else {
        printf("%d不是质数\n", n);
    }
    return 0;
}

1.3.埃拉托色尼筛法：

#include <stdio.h>

void eratosthenes(int n) 
{
    int prime[n + 1];
    for (int i = 2; i <= n; i++) 
    {
        prime[i] = 1;
    }
    for (int i = 2; i * i <= n; i++) 
    {
        if (prime[i]) 
        {
            for (int j = i * i; j <= n; j += i) 
            {
                prime[j] = 0;
            }
        }
    }
    printf("2");
    for (int i = 3; i <= n; i += 2) 
    {
        if (prime[i]) 
        {
            printf(", %d", i);
        }
    }
    printf("\n");
}

int main() 
{
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if (1 == n)
    {
        printf("1不是质数\n");
        return 0;
    }
    printf("%d以内的所有质数：\n", n);
    eratosthenes(n);
    return 0;
}

1.4.米勒-拉宾素性检验：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long power(long long a, long long n, long long p) 
{
    long long ans = 1;
    while (n > 0) 
    {
        if (n & 1) 
        {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        n >>= 1;
    }
    return ans;
}

int miller_rabin(long long n, int k) 
{
    if (n == 2 || n == 3) 
    {
        return 1;   // 质数
    }
    if (n == 1 || n % 2 == 0) 
    {
        return 0;   // 非质数
    }
    long long d = n - 1;
    while (d % 2 == 0) 
    {
        d /= 2; // 分解为 d * 2^r
    }
    for (int i = 0; i < k; i++) 
    {
        long long a = rand() % (n - 3) + 2; // 2 ~ n-2 之间随机选取一个数 a
        long long x = power(a, d, n);
        if (x == 1 || x == n - 1) 
        {
            continue;
        }
        int flag = 0;   // 判断循环中是否需要继续
        // 执行 r-1 次循环，检验是否有 x^d, x^2d, …, x^(2^(r-1)*d) 都与 n-1 同余
        for (long long r = d; r != n - 1; r <<= 1) 
        {
            x = (x * x) % n;
            if (x == 1) 
            {
                return 0;   // 是合数
            }
            if (x == n - 1) 
            {
                flag = 1;
                break;
            }
        }
        if (!flag) 
        {
            return 0;   // 是合数
        }
    }
    return 1;   // 是质数
}

int main() 
{
    long long n;
    int k;
    printf("请输入一个整数：");
    scanf("%lld", &n);
    printf("请设置测试次数 k：");
    scanf("%d", &k);
    int flag = miller_rabin(n, k);
    if (flag) 
    {
        printf("%lld是质数\n", n);
    } 
    else 
    {
        printf("%lld不是质数\n", n);
    }
    return 0;
}

解释一下这里的测试次数k:

在算法中随机选择不同的基数进行多次检测。通过增加测试次数 k，可以提高算法的准确性，减少错误判定合数为质数的可能性。在每次测试中，随机选择不同的基数进行检测，如果所有测试都通过，那么被检测的数更有可能是质数。总之k 的值决定了算法进行随机测试的次数，通过多次测试提高了判定质数的可靠性。（一般来说k的值选取范围是5-15）

1.5.线性筛法：

#include <stdio.h>

void linear_sieve(int n) 
{
    int prime[n + 1], cnt = 0;
    int factor[n + 1];
    for (int i = 2; i <= n; i++) 
    {
        if (!prime[i]) 
        {
            prime[i] = i;
            factor[i] = i;
            cnt++;
        }
        for (int j = 1; j <= cnt && prime[i] >= prime[j] && i * prime[j] <= n; j++) 
        {
            prime[i * prime[j]] = prime[j];
            if (prime[i] == prime[j]) 
            {
                factor[i * prime[j]] = factor[i] * factor[j];
            } 
            else 
            {
                factor[i * prime[j]] = factor[i] * prime[j];
            }
        }
    }
    printf("2");
    for (int i = 3; i <= n; i += 2) 
    {
        if (prime[i] == i) 
        {
            printf(", %d", i);
        }
    }
    printf("\n");
}

int main() 
{
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if (1 == n)
    {
        printf("1不是质数\n");
        return 0;
    }
    printf("%d以内的所有质数：\n", n);
    linear_sieve(n);
    return 0;
}

1.6.费马小定理：

费马小定理是一种用于判断质数的方法。如果一个数 $n$ 是质数，且 $a$ 是小于 $n$ 的任意正整数，则 $a^{n?1}\equiv 1(\mathrm{mod}n)$。

具体的判断方法为：随机选取一个整数 $a$，计算 $a^{n?1}\mathrm{mod}n$ 的值，如果等于1，则 $n$ 可能是质数。

但是，存在一些合数也满足费马小定理，即被称为费马伪素数。因此，费马小定理不是完全可靠的判断方法。需要进行多次测试，才能提高正确率。

下面是使用费马小定理进行判断的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long power(long long a, long long n, long long p) 
{
    long long ans = 1;
    while (n > 0) 
    {
        if (n & 1) 
        {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        n >>= 1;
    }
    return ans;
}

int fermat_primality_test(long long n, int k) 
{
    if (n == 2 || n == 3) 
    {
        return 1;   // 质数
    }
    if (n == 1 || n % 2 == 0) 
    {
        return 0;   // 非质数
    }
    for (int i = 0; i < k; i++) 
    {
        long long a = rand() % (n - 2) + 2; // 2 ~ n-1 之间随机选取一个数 a
        if (power(a, n - 1, n) != 1) 
        {
            return 0;   // 是合数
        }
    }
    return 1;   // 是质数
}

int main() 
{
    long long n;
    int k;
    printf("请输入一个整数：");
    scanf("%lld", &n);
    printf("请设置测试次数 k：");
    scanf("%d", &k);
    int flag = fermat_primality_test(n, k);
    if (flag) 
    {
        printf("%lld是质数\n", n);
    } 
    else 
    {
        printf("%lld不是质数\n", n);
    }
    return 0;
}

1.7.素性检验：

素性检验是一种比费马小定理更加精确的判断质数的方法，常用的有 Miller-Rabin 素性检验和 AKS 算法。

Miller-Rabin 素性检验已经在第四个示例中介绍过了，这里再介绍一下 AKS 算法。

AKS 算法是一种基于代数学理论的判断质数的算法，可以在多项式时间内实现。它的时间复杂度为 $O({\log }^{12}n)$，比 Miller-Rabin 算法还要慢，但是它的正确率非常高，可以判断非常大的质数。

AKS 算法的核心思想是利用柿子（binomial theorem）和模 p 下的同余关系，对多项式进行模运算，最终得到一个判断质数的结论。

这里不再给出 AKS 算法的代码实现，感兴趣的话可以自己百度一下。😉

2.在C语言中，求两个数的最大公约数的常见算法有以下几种：

1. 辗转相减法
2. 辗转相除法
3. Stein算法
4. 拓展

2.1.辗转相减法

辗转相减法也叫欧几里得算法，是求解两个正整数的最大公约数的一种简便算法，其基本思想是利用两数的差的绝对值不断递归，直到两数相等为止，此时所得的数即为最大公约数。

具体的实现过程为：

1. 如果两个数相等，则它们的最大公约数即为它们本身；
2. 如果其中一个数为0，则另一个数即为最大公约数；
3. 如果两个数都不相等且都不为0，则将它们中较大的数减去较小的数，并用得到的差替换较大的数，然后回到第1步。

以下是使用辗转相减法求两个数的最大公约数的实现：

#include <stdio.h>

int gcd(int a, int b) 
{
    if (a == b) 
    {
        return a;
    }
    if (a == 0) 
    {
        return b;
    }
    if (b == 0) 
    {
        return a;
    }
    if (a > b) 
    {
        return gcd(a - b, b);
    } 
    else 
    {
        return gcd(a, b - a);
    }
}

int main() 
{
    int a, b;
    printf("请输入两个数：");
    scanf("%d %d", &a, &b);
    int g = gcd(a, b);
    printf("%d 和 %d 的最大公约数是 %d\n", a, b, g);
    return 0;
}

2.2.辗转相除法

辗转相除法（欧几里得算法）在C语言中的实现可以采用迭代或递归两种方式。

2.2.1.迭代实现：

#include <stdio.h>

int gcd(int a, int b) 
{
    while (b != 0) 
    { // 当b不为零时继续循环
        int temp = a % b; // 计算a除以b的余数
        a = b; // 将b赋值给a，准备下一轮迭代
        b = temp; // 将上一轮的余数赋值给b
    }
    return a; // 循环结束后，a即为最大公约数
}

int main() 
{
    int num1, num2;
    
    printf("请输入两个整数：");
    scanf("%d %d", &num1, &num2);

    // 确保num1总是较大的数，这样可以简化逻辑
    if (num1 < num2) 
    {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }

    int result = gcd(num1, num2);
    printf("这两个数的最大公约数是：%d\n", result);

    return 0;
}

2.2.2.递归实现：

#include <stdio.h>

int gcd(int a, int b) 
{
    // 当b为0时，a即为最大公约数
    if (b == 0)
        return a;
    else
        // 递归调用gcd函数，将b作为新的a，a除以b的余数作为新的b
        return gcd(b, a % b);
}

int main() 
{
    int num1, num2;

    printf("输入两个整数: ");
    scanf("%d %d", &num1, &num2);

    // 输出两个数的最大公约数
    printf("The GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));

    return 0;
}
  

2.3. Stein算法

Stein算法，也叫二进制 GCD 算法，是一种用于计算两个正整数的最大公约数的算法。它比辗转相除法更加高效，因为它的操作只涉及移位、加减运算和条件选择，消耗的时间和空间都比辗转相除法少。

具体的实现过程为：

1. 把两个数都右移一位，直到两个数都为奇数；
2. 如果a<b，则交换a和b；
3. 计算d=a-b，如果d=0，则a即为最大公约数，结束；
4. 把d右移一位，即d=d/2；
5. 重复步骤3-4，直到d=1；
6. 求出a和b的公共因子2的k次幂，即g=2^k，其中k是使a和b均为偶数的因子，把a和b都右移k位，此时就回到步骤1。

以下是使用Stein算法求两个数的最大公约数的实现：

#include <stdio.h>

int gcd(int a, int b) 
{
    if (a == 0 || b == 0) 
    {
        return a + b;
    }
    int k = 0;
    while ((a & 1) == 0 && (b & 1) == 0) 
    {
        a >>= 1;
        b >>= 1;
        k++;
    }
    while ((a & 1) == 0) 
    {
        a >>= 1;
    }
    do {
        while ((b & 1) == 0)
        {
            b >>= 1;
        }
        if (a > b) 
        {
            int t = b;
            b = a;
            a = t;
        }
        b -= a;
    } while (b != 0);
    return a << k;
}

int main() 
{
    int a, b;
    printf("请输入两个数：");
    scanf("%d %d", &a, &b);
    int g = gcd(a, b);
    printf("%d 和 %d 的最大公约数是 %d\n", a, b, g);
    return 0;
}

Stein算法比辗转相减法和辗转相除法更加高效，特别是在处理大整数时。

2.4.Lehmer算法和Sch?nhage-Strassen算法

除了辗转相减法、辗转相除法和Stein算法外，还有更好的算法，例如，它们能够在O(N(logN)^2)的时间复杂度内计算出两个N位整数的最大公约数，但是实现起来比较复杂，需要涉及到高精度计算和复杂的数论知识。

Lehmer算法是一种基于欧几里得算法的改进算法，它利用了欧几里得算法的思想，但是通过一些优化使得执行次数更少，效率更高。它的基本思想是先对两个数进行预处理，然后再利用这些预处理结果进行计算。

Sch?nhage-Strassen算法是一种基于快速傅里叶变换的算法，它能够在O(N(logN)^2)时间复杂度内计算出两个N位整数的最大公约数。它的基本思想是把计算最大公约数的问题转化为计算多项式的问题，然后利用快速傅里叶变换进行多项式的乘法和除法。

2.4.1.Lehmer算法

下面是使用Lehmer算法求两个数的最大公约数的实现：

#include <iostream>
#include <vector>
using namespace std;

// 求p^n
int pow(int p, int n)     
{
    int res = 1;
    for (int i = 0; i < n; i++) 
    {
        res *= p;
    }
    return res;
}

// 把n表示成p进制的形式，返回各个位的系数
vector<int> convert(int n, int p) 
{
    vector<int> digits;
    while (n > 0) 
    {
        digits.push_back(n % p);
        n /= p;
    }
    return digits;
}

// Lehmer算法
int lehmer(int a, int b) 
{
    if (a == 0 || b == 0) 
    {
        return a + b;
    }
    int p = 10, q = pow(p, 1.5);
    vector<int> r = convert(a, p), s = convert(b, p);
    int n = r.size(), m = s.size();
    while (m > 0) 
    {
        int t = n - m;
        int k = r[n - 1] * q + r[n - 2];
        int l = s[m - 1] * q + s[m - 2];
        if (r[n - 1] == s[m - 1] && k < l * q || k < l * q - 1) 
        {
            t--;
            k = (k + p * r[n - 3]) * p + r[n - 4];
        }
        int u = (k - l) % q * pow(p, t);
        if (k < l) 
        {
            u -= pow(p, t + 1);
        }
        r.erase(r.begin() + t, r.end());
        for (int i = 0; i < m - 1; i++) 
        {
            r[i] -= u * s[i];
            if (r[i] < 0) 
            {
                r[i] += p;
                r[i + 1]--;
            }
        }
        while (r.back() == 0) 
        {
            r.pop_back();
        }
        n = r.size();
        swap(r, s);
        swap(m, n);
    }
    return s[0];
}

int main() 
{
    int a, b;
    cout << "请输入两个数：";
    cin >> a >> b;
    int g = lehmer(a, b);
    cout << a << " 和 " << b << " 的最大公约数是 " << g << endl;
    return 0;
}

注意：

我这个windows上面的wsl没有装这个头文件，大家可以在ubuntu虚拟机里面试一试，这个有时间再弄

2.4.2. Sch?nhage-Strassen算法

下面是使用Sch?nhage-Strassen算法求两个数的最大公约数的实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;

const double PI = acos(-1);
typedef complex<double> comp;

void bit_reverse_copy(const vector<comp>& a, vector<comp>& b) 
{
    int n = a.size();
    int p = 0;
    for (int i = 0; i < n; i++) 
    {
        b[p] = a[i];
        for (int j = n / 2; (p ^= j) < j; j /= 2);
    }
}

// 快速傅里叶变换
void fft(vector<comp>& a, int inv) 
{
    int n = a.size();
    vector<comp> b(n);
    bit_reverse_copy(a, b);
    for (int h = 1; h < n; h <<= 1) 
    {
        for (int j = 0; j < n; j += h << 1) 
        {
            comp w(1, 0);
            for (int k = 0; k < h; k++) 
            {
                comp t = w * b[j + k + h];
                b[j + k + h] = b[j + k] - t;
                b[j + k] += t;
                w *= comp(cos(PI * inv * k / h), sin(PI * inv * k / h));
            }
        }
    }
    if (inv == -1) 
    {
        for (int i = 0; i < n; i++) 
        {
            b[i] /= n;
        }
    }
    a.swap(b);
}

// 计算两个N位整数的最大公约数
int ss_gcd(string a, string b) 
{
    int n = a.size(), m = b.size();
    int N = 1;
    while (N < n + m) 
    {
        N <<= 1;
    }
    vector<comp> A(N), B(N);
    for (int i = 0; i < n; i++) 
    {
        A[i] = a[n - 1 - i] - '0';
    }
    for (int i = 0; i < m; i++) 
    {
        B[i] = b[m - 1 - i] - '0';
    }
    fft(A, 1);
    fft(B, 1);
    vector<comp> C(N);
    for (int i = 0; i < N; i++) 
    {
        C[i] = A[i] * B[i];
    }
    fft(C, -1);
    reverse(C.begin() + 1, C.end());
    while (C.size() > 1 && C.back().real() == 0) 
    {
        C.pop_back();
    }
    string r;
    for (int i = C.size() - 1; i >= 0; i--) 
    {
        r += char(C[i].real() + 0.5) + '0';
    }
    while (r.size() > 1 && r.back() == '0') 
    {
        r.pop_back();
    }
    return stoi(r);
}

int main() 
{
    string a, b;
    cout << "请输入两个数：";
    cin >> a >> b;
    int g = ss_gcd(a, b);
    cout << a << " 和 " << b << " 的最大公约数是 " << g << endl;
    return 0;
}

注意：

我这个windows上面的wsl没有装这个头文件，大家可以在ubuntu虚拟机里面试一试