Problem 7: Find the 10001st prime.

Problem #7 var lite tråkigt. Min is_prime() är inte optimal direkt. Följande fakta borde ha implementerats också:

• 1 är inte ett primtal.


• Alla primtal utom 2 är udda.


• Givet n kan bara ha en primtalsfaktor större än sqrt(n).

Min lösning:

#include <iostream>

template <typename T>
inline bool is_prime(T p)
{
  for (T i = 2; i < p; ++i)
    if (!(p % i))
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 10001; 
  for (int pnum = 0, i = 2;; ++i)
  {
    if (is_prime(i))
    {
      pnum++;
      if (pnum == n)
      {
        std::cout << "Answer is " << i << std::endl;
        return 0;
      }
    }
  }
}

Godnatt!