c - 为什么不使用大于 10 位的数字？

Question

你好社区我有以下问题以下代码对于超过10位的数字没有收敛到任何解决方案，并且不知道问题出在哪里，因为知道该数字是素数将在一次调用中满足费马小定理功能。

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

unsigned long exp_mod(unsigned long x, unsigned long y, unsigned long n)
{
    unsigned long s,t,u;
    int i;
    s=1; t=x; u=y;
    while(u) {
        if (u&1) s=(s*t)%n;
        u>>=1;
        t=(t*t)%n;
    }
    return s;
}

int main(){
    unsigned long number,a,b;
    int i;
    printf("introduce number to test\n");
    scanf("%lu",&a);
    number=a;
    srand((unsigned int)time(0));

    while (1) {
        a=rand()%(number-1)+2;//0<a<number
        b=exp_mod(a,number-1,number);
        if ( b==1 ) {
            printf ("by Fermat:  %lu is prime\n",number);
            break;
        }
    }
    return 0;
}

有什么建议吗？问候

Answer 1

在大多数编译器和系统上，unsigned long 的大小为 32 位，因此大约为 4 * 10^9 - 这就是它无法处理 10 位数字的原因。 只需将 unsigned long 更改为 unsigned long long int 即可。