-5

示例代码：

bool is_special_prime (int N) {
  QHash<int, int> o;
  struct A_functor
  {
    int operator()(unsigned int n) { return n >> __builtin_ctz(n);}
  }A;
  int k = A(N + 1);
  if(k == 1)
    return 0;
  o[k] = k;
  int t = (N - 5) >> 1;
  for(int i = 0; i < t; i++) {
      k = A(N + k);
      if(k == 1 || o.contains(k))
        return 0;
      o[k] = k;
  }
  return 1;
}

这种方式是否可以测试大于最新最大素数 2 ^ 57885161 - 1 的数字？

4

3 回答 3

2

你读过关于卢卡斯-莱默的书吗？听起来您在寻找新的更快的方法来测试素数之前还需要做更多的研究。首先尝试使用 bignum 库实现 Lucas-Lehmer。

您的算法迭代到 N/2，远非快速，实际上它确实非常慢（比素数慢得多）。它也永远找不到大于 2^32 或 2^64 的素数，这比 2^57885161 小很多。你明白为什么它这么慢吗？它不能返回 1，直到它循环 i 小于 N/2 的值。

我还没有检查你的代码是否准确地确定了素数。

于 2013-05-03T12:37:22.630 回答
1

这种方式是否可以测试大于最新最大素数 2 ^ 57885161 - 1 的数字？

如果您碰巧使用int至少 57885162 位宽的平台，那么可以（假设您的算法是正确的，我没有费心检查）。

现在，让我们严肃点几秒钟：现在消费级计算机最多使用 64 位宽的整数，你可以看到从那个假设的平台来看它是一个很长的镜头......

如果你想执行这样的计算，你需要用 BigNum 库替换int（一路上也会有其他的限制——振作起来）。

于 2013-05-03T12:17:31.003 回答
1

您传递的int类型可以在-2^31 to 2^31-132 位系统上保存范围内的数字。你不能用它来测试你提到的一些订单

于 2013-05-03T12:12:34.280 回答