4

代码：

void prime()    
{    
    int i,N;    
    scanf("%d",&N);    
    for(i=2;i<N;i++)            
    {    
        if (((i^(N-1))%N )==1);     
        else{    
            printf("not prime");   
            return;
        }     
    }    
    printf("prime");    
    return;    
}

该程序基于关于素数的费马定理。N 是要作为素数进行测试的数。该程序未显示“11”的正确结果。也许是由于我没有发现的一些错误。

4

4 回答 4

2

如果这是伪代码 或
如果是 C 代码，则您将遇到溢出，使用^as 幂运算符无效。

使用大整数很快成为 C 中的一个问题。有各种BigInt可用的库。

对于大整数计算，使用浮点是具有挑战性的。建议避免double,pow()等。

由于问题都是 >= 0，建议使用无符号整数。也使用可用的最大整数类型 - 通常unsigned long long。由于溢出是一种真实的可能性，请检测它。

unsigned long long upower(unsigned i, unsigned N) {
  unsigned long long power = 1;
  if (i <= 1) return i;
  while (N-- > 0) {
    unsigned long long power_before = power;
    power *= i;
    if (power < power_before) {
      printf("Overflow\n");
      return 0;
    }
  }
  return power;
}

void prime() {
  unsigned i, N;
  scanf("%u", &N);
  for (i = 2; i < N; i++) {
    if ((upower(i, N - 1) % N) != 1) {
      printf("not prime");
      return;
    }
  }
  printf("prime");
  return;
}

代替大整数，中国剩余定理 可能会提供一个替代方案(upower(i, N - 1) % N) != 1。

于 2013-10-09T14:08:19.393 回答
1

如果我将您的代码读为伪代码，那么您就溢出了。

10^10大于2^31 -1大多数的最大值int。你可以通过使用 long 来解决这个问题N=11，但这不会让你走得太远，你也会在某个时候开始溢出。

这个定理，至少是这样表达的，对于有限长度的数字来说是非常不切实际的。

现在，如果您的代码是真实的C，请注意这^意味着XOR，而不是求幂。幂是pow()。感谢评论者指出这一点。

于 2013-10-09T07:36:11.173 回答
0

在这里可以应用模块化数学规则和原理来表明，为了计算

(i ^ (N-1)) % N,

您甚至不需要首先计算 i^(N-1) 。您可以轻松地将 (N-1) 分解为2的幂。让我们举一个例子来更清楚地说明。

假设我们的素性测试的主题，N = 58。

所以，

N - 1 = 57

57 可以很容易地改写为：

57 = 1 + 8 + 16 + 32

或者，

57 = 2^0 + 2^3 + 2^4 + 2^5

所以，用这个值代替N-1，我们需要计算

(i ^ (2^0 + 2^3 + 2^4 + 2^5))% 58

或者，

((i^1) × (i^8) × (i^16) × (i^32))% 58

其中，使用模乘恒等式，可以重写为：

((i^1)% 58 × (i^8)% 58 × (i^16)% 58 × (i^32)% 58) mod 58 ---(1)

注意，

(i^1)% 58 = i%58

可以很容易地计算而不用担心任何溢出。

再次利用模乘恒等式，我们知道

(i^2)% 58 = ((i^1)% 58 × (i^1)% 58)% 58

代入(i^1)%58的值，求(i^2)%58。

您可以继续以这种方式计算 (i^4)% 58 到 (i^32)% 58。一旦完成，您最终可以替换 (1) 中的值以最终找到所需的值，非常有效地避免任何溢出。

请注意，还存在其他模幂技术。这只是展示如何使用模块化数学技术来实现费马的小素性检验的一个例子。

干杯!

于 2016-06-26T18:14:30.873 回答
0

很抱歉稍微更改您的代码。使用 BigInteger 类，您可以非常快速地计算更大的数字。但是，您可以使用此方法不按顺序获取素数，而是测试是否有任何数字是素数。

using System;
using System.Numerics;
                    
public class Program
{
    public static void Main()
    {
        Console.WriteLine(2);
        for(var i = 3; i < 100000; i+=2) 
        {
            if(BigInteger.ModPow(2, i , i) == 2)
                Console.WriteLine(i);
        }
    }
}

https://dotnetfiddle.net/nwDP7h

当它落入以下数字时，此代码将产生错误结果。

https://oeis.org/a001567 https://oeis.org/a006935

要修复这些错误，您需要如下编辑代码并在这些数字中进行二进制搜索以测试该数字是否为伪素数。

public static bool IsPrime(ulong number)
{
    return number == 2
        ? true
        : (BigInterger.ModPow(2, number, number) == 2
            ? (number & 1 != 0 && BinarySearchInA001567(number) == false)
            : false)
}

public static bool BinarySearchInA001567(ulong number)
{
    // Is number in list?
    // todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
    // Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}
于 2020-07-19T00:21:36.743 回答