c++ - 查找第 10001 个素数时出错

Question

我目前正在尝试解决项目欧拉的问题之一，以找到第 10001 个素数。虽然我的代码没有返回正确的数字，甚至在我更改“count”的起始值时返回了偶数。以下是我的代码，如果有人可以帮助我解决这个问题，将不胜感激。

#include <math.h>
#include <iostream>
#include <stdbool.h>
using namespace std;

bool isPrime(int num);

int main()
{
    int num = 0, count = 0;
    while(count < 10001)
    {
        num++;
        while(isPrime(num) != true)
        {
               num++;
               cout << "\n num: " << num;   
        }
        count++;
        isPrime(12);
    }
    cout << "the 10001's prime number is: " << num << "\n " << count;
    system("pause");
    return 0;
}


bool isPrime(int num)
{
       bool checkPrime = false;
       if(num%2 != 0)
       {
              for(int i = 3; i <= sqrt(num); i++)
              {
                      if(num%i != 0)
                      {
                              checkPrime = true;
                      }
                      else
                      {
                          checkPrime = false;
                          break;   
                      }       
              }  
       }
       else
       {
           return false;   
       }
       if(checkPrime)
       {
              return true;    
       }
       else
       {
           return false;    
       }      
}

Answer 1

您在 isPrime 中的逻辑是错误的。例如，isPrime(3) 返回 false。基本问题是您将 checkPrime 初始化为 false 而不是 true，因此任何未进入 for 循环的小数即使是素数也会返回 false。

这是一个（希望是）正确的版本，还有 Dukeling 建议的一些更改。

bool isPrime(int num)
{
    if (num < 2) // numbers less than 2 are a special case
        return false;
    bool checkPrime = true; // change here
    int limit = sqrt(num);
    for (int i = 2; i <= limit; i++)
    {
        if (num%i == 0)
        {
            checkPrime = false;
            break;   
        }       
    }  
    return checkPrime;
}