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

发布时间:2024年01月16日

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 n n 是质数,且 a a a 是小于 n n n 的任意正整数,则 a n ? 1 ≡ 1 ( m o d n ) a^{n-1} \equiv 1 \pmod n an?11(modn)

具体的判断方法为:随机选取一个整数 a a a,计算 a n ? 1 ? m o d ? n a^{n-1} \bmod n an?1modn 的值,如果等于1,则 n n 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 ) O(\log ^{12} n) O(log12n),比 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虚拟机里面试一试

文章来源:https://blog.csdn.net/weixin_51604843/article/details/135627432
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。