C语言 设计并实现一种大素数随机生成方法； 实现一种快速判定任意一个大数是否是素数方法 跪求啊

C语言 设计并实现一种大素数随机生成方法； 实现一种快速判定任意一个大数是否是素数方法 跪求啊

目前来说大素数随机生成方法是不存在的，这是一个NPC问题，NPC问题世界的七大难题之一，如果你能够解决，就能够拿到100万美金的奖励。但是现在有快速判定任意一个大数是否是素数方法：Miller Rabin算法。
Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时， Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin 算 法底层运算的优化，可以取得较以往实现更好的性能。Miller-Rabin算法是Fermat算法的一个变形改进，它的理论基础是由Fermat定理引申而来。
Fermat 定理： n是一个奇素数，a是任何整数(1≤ a≤n-1) ，则 a^(n-1)≡1(mod n)。
Miller-Rabin 算法的理论基础：如果n是一个奇素数， 将n-1表示成2^s*r的形式(r是奇 数)，a 是和n互素的任何整数， 那么ar≡1(mod n) 或者对某个j(0≤j ≤s －1， j∈Z) 等式 a2jr ≡－1(mod n)成立。 这个理论是通过一个事实经由Fermat定理推导而来： n是一个奇素数，则方程x2 ≡ 1 mod n只有±1两个解。

int main(void)
{
    int a, i;        
    
    srand(time(NULL));  
    a = rand();
    if (a > 5)
    if (a%2==0 || a%3==0 || a%5==0)
    {
         printf("%d是个合数 ", a);
         return 0;
    }
    else
    {
        printf("%d是个素数 ", a);
        return 0;
    }
    if (a == 1)
    {
        printf("1既不是合数,也不是素数 ");
    }
    for (i=2; i<=a; i++)
        if (0 == a%i)
            break;
    if (a == i)
        printf("%d是个素数 ", a);
    else
        printf("%d是个合数 ", a);

    return 0;
}

程序主要思路:

随机出数字, 然后再定义一个变量. 先判断这个随机出的数字能不能被2,3,5整除, 如果可以, 直接输出, 然后退出程序. 如果不能, 让它为2(因为0不能作除数, 任何整数都能整除1), 然后让它一直自加, 直到和输入的数字一样.

如果自加过程中用户输入的数字能够把这个数字整除, 就结束自加(退出循环), 然后再判断自加的这个数和输入的数是否相等, 如果相等, 说明这个数之前的所有数都不能被整除, 那就是质数. 如果不相等, 说明这个数有2个以上的因数, 则是合数.

另:素数和质数是一个意思.