迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 编程语言 > C++ >

在 C++ 中检查一个数字是否为质数

作者:迹忆客 最近更新:2023/03/15 浏览次数:

本文将介绍几种方法在 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 是大于零的整数。它进一步意味着,有效的方法恰好是测试 23 的数值可除性。如果先前的条件没有消除给定的数字不是质数,则应测试所有形式为 6k+-1 的数字,该数字也应小于 n 的平方根。请注意,例如当终端中断被捕获时(比如Ctrl+D),validateInputwhile 循环中断。

#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);
}

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

Arduino 中停止循环

发布时间:2024/03/13 浏览次数:444 分类:C++

可以使用 exit(0),无限循环和 Sleep_n0m1 库在 Arduino 中停止循环。

Arduino 复位

发布时间:2024/03/13 浏览次数:315 分类:C++

可以通过使用复位按钮,Softwarereset 库和 Adafruit SleepyDog 库来复位 Arduino。

Arduino 的字符转换为整型

发布时间:2024/03/13 浏览次数:181 分类:C++

可以使用简单的方法 toInt()函数和 Serial.parseInt()函数将 char 转换为 int。

Arduino 串口打印多个变量

发布时间:2024/03/13 浏览次数:381 分类:C++

可以使用 Serial.print()和 Serial.println()函数在串口监视器上显示变量值。

Arduino if 语句

发布时间:2024/03/13 浏览次数:123 分类:C++

可以使用 if 语句检查 Arduino 中的不同条件。

Arduino ICSP

发布时间:2024/03/13 浏览次数:214 分类:C++

ICSP 引脚用于两个 Arduino 之间的通信以及对 Arduino 引导加载程序进行编程。

使用 C++ 编程 Arduino

发布时间:2024/03/13 浏览次数:127 分类:C++

本教程将讨论使用 Arduino IDE 在 C++ 中对 Arduino 进行编程。

Arduino 中的子程序

发布时间:2024/03/13 浏览次数:168 分类:C++

可以通过在 Arduino 中声明函数来处理子程序。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便