C++如何使用返回布尔值的函数来确定素数

Question

#include <iostream>
#include <iomanip>
using namespace std;

int  main()
{
   int  number;
   int count = 0;

   cout << "Enter an integer between 1 and 100: ";
   cin >> number;

   while (number < 0 || number > 100)
   {
      cout << "Invalid number." << endl;
      cout << "Enter an integer between 1 and 100: ";
      cin >> number;
   }

   cout << "The first " << number << " primes: \n" << endl;

   for (int i = 2; number > 0; ++i)
   {
      bool  isPrime = true;
      for (int j = 2; j < i; ++j)
      {
         if (i  % j == 0)
         {
            isPrime = false;
            break;
         }
      }
      if (isPrime)
      {
         count++;
         --number;
         cout << setw(5) << i;
         if (count % 10 == 0)
            cout << endl;
      }
   }
   cout << endl;
   system("pause");
   return 0;
}

Answer 1

你似乎在测试i%j比i低的每一个j。但是如果您测试j=3，那么您可以排除所有3的倍数。当一个数不能被3除时，它就不能被6除。这将提高性能。

您还可以实现AKS primalty测试https://en.wikipedia.org/wiki/aks_primality_test，这可能需要更多的工作。我不知道这个测试的细节，但它是确定性的，对所有数字都有效。

如果您想要一个函数bool isPrime（int number）,您可以从您的main方法中提取以下代码,它看起来如下所示：

bool isPrime(int number){
    for (int j = 2; j < number/2; ++j)
    {
        if (number % j == 0)
        {
            return false;
        }
    }
    return true;
}

   for (int i = 2; number > 0; ++i)
   {
      if (isPrime(i))
      {
         count++;
         --number;
         cout << setw(5) << i;
         if (count % 10 == 0)
            cout << endl;
      }
   }