利用gmp库实现大数计算的一道题目

Question

我的想法是，首先遍历大数n得到小于n的所有m值，然后对每个m值与n利用gmp库自带的gcd函数计算出最大公约数，如果是1，那么他们就是互素的，euler值就+1，可是遍历n是不现实的，n是个最高长达512比特的大数，加载一天都不知道能不能加载出来，这让我不知所措，请问到底如何实现这个题呢？

对于这道题，我的代码如下：

#include<gmp.h>
#include<iostream>
using namespace std;
int main()
{
    mpz_t p, q;
    mpz_init(p); //初始化q和p大素数
    mpz_init(q);

    //生成大素数算法
    gmp_randstate_t grt;
    gmp_randinit_default(grt); //设置随机数生成算法为默认
    gmp_randseed_ui(grt, time(NULL)); //设置随机化种子为当前时间

    mpz_urandomb(p, grt, 512);//随机生成一个0 ———（2^512）- 1（即512个bit上都是1）的一个大数
    mpz_urandomb(q, grt, 512);

    //利用mpz_t p, q生成素数mpz_t p, q
    mpz_nextprime(p, p);  //使用GMP自带的素数生成函数
    mpz_nextprime(q, q);
    gmp_printf("%ZX\n\n", p);
    gmp_printf("%ZX\n\n", q);

    //计算p*q的值，并存放在n中
    mpz_t n;
    mpz_init(n);
    mpz_mul(n, p, q); //计算p*q
    gmp_printf("%ZX\n\n", n);

    //计算euler值
    mpz_t euler,rop,m;
    mpz_init(euler);
    mpz_init(rop);
    mpz_init(m);

    //这里需要先遍历n,得到m值 （×） =》太理想化，遍历n同样是不现实的 
    while (1)
    {
        mpz_add_ui(m,m,1);//m=m+1
        if (mpz_cmp(m, n) > 0)
        {
            break;
        }

        //计算m与n之间的最大公约数，可以用gmp库自带的gcd函数
        mpz_gcd(rop, m, n);
        if (mpz_cmp_ui(rop, 1) == 0)//最大公约数为1，则为互素
        {
            //mpz_set(euler, euler + 1); 这个会直接报错
            mpz_add_ui(euler, euler, 1);//euler=euler+1
            gmp_printf("%ZX\n\n", euler);
        }

    }
    gmp_printf("%ZX\n\n", euler);

    //必须释放内存，不然就会报错
    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(m);
    mpz_clear(n);
    mpz_clear(rop);
    mpz_clear(euler);

}

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。


因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。