素测试算法无法正常工作

Question

>我有一个主要的测试算法，这是我从欧拉项目得到的，但是当43作为输入传递时，它返回false。伪代码在概述中给出，我将其转换为 c++ 代码。我可能在转换伪代码时犯了一个错误。算法的实际问题是什么？

#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int n)
{
    if(n <= 1)
    {
         return false;
    }
    else if(n < 4)
    {
        return true;
    }
    else if(n % 2 == 0)
    {
        return false;
    }
    else if(n < 9)
    {
        return true;
    }
    else if(n % 3 == 0)
    {
        return false;
    }
    else
    {
        int r = sqrt(n);
        int f = 5;
        while(f <= r)
        {
            if(n % f == 0)
            {
                return false;
            }
            if((n + 2) % f == 0)
            {
                return false;
            }
            f = f + 6;
        }
       return true;
    }
}
int main()
{
    cout << is_prime(43);
    system("PAUSE");
    return 0;
}

Answer 1

你的算法是正确的，但这里有以下错误

       if((n + 2) % f == 0)  //wrong
        {
            return false;
        }

应该是

      if(n%(f+2) == 0)  //Right
        {
            return false;
        }

Answer 2

您有算法错误。而不是 (n+2)%f 应改为 n%(f+2)

Answer 3

其他人指出了你的错误。 您可以稍微简化代码，减少所有这些if语句：

bool is_prime(int n)
{
  if(n <= 1)
  {
     return false;
  }
  if(n % 2 == 0)
  {
    return n == 2;
  }
  if(n % 3 == 0)
  {
    return n == 3;
  }
  // Check for factors of 5, 7, ...