判断一个数是否为素数

Question

我已经阅读了很多关于这个主题的代码，但是它们中的大多数产生的数字一直是素数，直到输入数字。但是，我需要只检查给定输入数字是否为素数的代码。

这是我能够写的，但它不起作用：

 void primenumber(int number)
{
    if(number%2!=0)
      cout<<"Number is prime:"<<endl;
    else
      cout<<"number is NOt prime"<<endl;
}

如果有人能给我关于如何使这项工作正常工作的建议，我将不胜感激。

更新

我对其进行了修改以检查 for 循环中的所有数字。

 void primenumber(int number)
{
    for(int i=1; i<number; i++)
    {
       if(number%i!=0)
          cout<<"Number is prime:"<<endl;
       else
          cout<<"number is NOt prime"<<endl;
    }
}

原文由 carla 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

你需要做更多的检查。现在，您只检查数字是否可以被 2 整除。对 2、3、4、5、6，… 执行相同操作，直到 number 。提示：使用 循环。

解决此问题后，请尝试寻找优化。提示：您只需检查所有数字，直到数字的平方根

原文由 Pablo Santa Cruz 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

素数测试中有 许多 潜在的优化。

然而，这里的 许多 答案，不仅 O(sqrt(n)) 更糟糕，而且还遭受 未定义行为(UB) 和不正确功能的困扰。

一个简单的素数测试：

 // Return true when number is a prime.
bool is_prime(int number) {
  // Take care of even values, it is only a bit test.
  if (number % 2 == 0) {
    return number == 2;
  }

  // Loop from 3 to square root (n)
  for (int test_factor = 3; test_factor <= number / test_factor; test_factor +=
      2) {
    if (number % test_factor == 0) {
      return false;
    }
  }
  return n > 1;
}

• 不要使用 test_factor * test_factor <= number 。对于大素数，它存在有 符号 整数溢出 (UB) 的风险。

• 好的编译器会看到附近的 number/test_factor 和 number % test_factor 并发出代码，计算两者的时间成本大约为一个。如果仍然担心，请考虑 div() 。

• 避免 sqrt(n) 。弱浮点库不能完全按照我们对这个整数问题的需要执行此操作，可能返回一个比预期整数小得多的值。如果仍然对 sqrt() 感兴趣，请在循环前使用 lround(sqrt(n)) 一次。

• 避免 sqrt(n) 宽整数类型 n 。将 n double 可能会丢失精度。 long double 可能不会更好。

• 测试以确保主要测试代码在 1、0 或任何负值时不会表现不佳或不正确。

• 考虑 bool is_prime(unsigned number) 或 bool is_prime(uintmax_t number) 用于扩展范围。

• 避免使用大于平方根 n 且小于 n 的候选因子进行测试。这样的测试因素绝不是 n 的因素。不遵守这一点会导致代码 _变慢_。

• 一个因素更可能是一个小值而不是一个大值。首先测试小值通常对非素数来说效率更高。

• 迂腐：避免 if (number & 1 == 0) { 。当 number < 0 并用稀有补码编码时，这是一个不正确的测试。使用 if (number % 2 == 0) { 并相信你的编译器会发出好的代码。

---

更先进的技术使用已知/发现的素数列表和 埃拉托色尼筛法。

原文由 chux - Reinstate Monica 发布，翻译遵循 CC BY-SA 4.0 许可协议