迹忆客 专注技术分享

本文将介绍几种方法在 C++ 中检查数字是否为质数。

在 C++ 中使用试除法检查数字是否为质数

质数测试是确定给定数字是否为质数的算法名称。检查数字是否为质数的简单解决方案是将自然数从一个数字迭代到给定的数字，并检查除法是否没有余数。

一些见解可以改进此方法。第一个-所有整数 n 的除数小于或等于 n/2，这意味着搜索空间已减小。在下面的示例中，我们还实现了一个 validateInput 函数，以从用户那里获取整数并验证该整数是否已成功存储在相应的变量中。该程序在无限循环中运行，不断向用户询问该号码，然后将消息打印到 cout 流中。

#include <iostream>
#include <string>
#include <algorithm>

using std::cout; using std::cin;
using std::endl; using std::string;
using std::numeric_limits;

bool isPrime(unsigned long long &n)
{
    if (n <= 1)  return false;

    for (uint i = 2; i < n; ++i)
        if (n % i == 0)
            return false;

    return true;
}

template<typename T>
T &validateInput(T &val)
{
    while (true) {
        cout << "Enter the natural number: ";
        if (cin >> val) {
            break;
        } else {
            if (cin.eof())
                exit(EXIT_SUCCESS);

            cout << "Enter a valid natural number!\n";
            cin.clear();
            cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
        }
    }
    return val;
}

int main(){
    unsigned long long num;

    while (true) {
        validateInput(num);

        isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
    }

    exit(EXIT_SUCCESS);
}

C++ 中使用相对优化的方法来检查数字是否为质数

我们可以通过仅测试小于或等于 n 的平方根的除数来继续优化先前的方法，这对所有自然数都成立。请注意，所有大于 3 的质数都可以表示为 6k+-1 的形式，其中 k 是大于零的整数。它进一步意味着，有效的方法恰好是测试 2 和 3 的数值可除性。如果先前的条件没有消除给定的数字不是质数，则应测试所有形式为 6k+-1 的数字，该数字也应小于 n 的平方根。请注意，例如当终端中断被捕获时（比如Ctrl+D），validateInput 从 while 循环中断。

#include <iostream>
#include <iostream>
#include <string>
#include <algorithm>

using std::cout; using std::cin;
using std::endl; using std::string;
using std::numeric_limits;

template<typename T>
T &validateInput(T &val)
{
    while (true) {
        cout << "Enter the natural number: ";
        if (cin >> val) {
            break;
        } else {
            if (cin.eof())
                exit(EXIT_SUCCESS);

            cout << "Enter a valid natural number!\n";
            cin.clear();
            cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
        }
    }
    return val;
}

bool isPrime(unsigned long long &n)
{
    if (n <= 3)
        return n > 1;

    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

int main(){
    unsigned long long num;

    while (true) {
        validateInput(num);

        isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
    }

    exit(EXIT_SUCCESS);
}