C++大学教程(第九版)6.29素数

2024-01-22 20:04

本文主要是介绍C++大学教程(第九版)6.29素数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

(素数)素数是只能被1和自已整除的整数。例如,235和7是素数而468和9不是素数
a)编写一个函数,确定一个数是否是素数。
b)在程序中使用这个函数,该程序确定和打印2 ~10000之间的所有素数。在确信已找到所有的素数之前,实际需测试这些数中的多少个数?
c)起初,你可能认为 n/2 是确定一个数是否为素数所要进行的最多的测试次数,但是实际上只需要进行n的平方根次就可以了。为什么呢?重新编写程序,用这两种方式运行。估计性能提高了多少。

b)代码

b)实际需要测试这些数中的5000个,满足条件的代码如下:
增加了计算程序运行时间的部分。

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;bool isPrime(int);int main()
{clock_t startTime, endTime;startTime = clock();int count = 0;for (unsigned long long i = 2; i <= 10000; i++){if (isPrime(i)){cout << setw(4) << i << "\t"; //<< (isPrime(i) ? "是素数" : "")count++;if (count != 0 && count % 10 == 0){cout << endl;}}}endTime = clock();cout << "\nThe run time is " << static_cast<double>(endTime - startTime) / CLOCKS_PER_SEC<< "s." << endl;return 0;
}bool isPrime(int n)
{bool flag = true;for (int i = 2; i < n; i++){if (n % i == 0)flag = false;}return flag;
}

运行截图

可以看到程序运行时间0.481s
在这里插入图片描述在这里插入图片描述

c)代码

修改了判断素数的函数代码,并计算了程序运行时间。

思想:素数的因子只有1和它本身。 如果数c不是素数,则还有其他因子。设a,b中定有一个大于sqrt( c ) ,一个小于sqrt( c ) 。所以m一定有一个小于等于其平方根的因数,那么验证素数时就只需要验证到其平方根就可以了。

#include <iostream>
#include <iomanip>
#include <cmath>
#include <ctime>
using namespace std;bool isPrime(unsigned long);int main()
{clock_t startTime, endTime;startTime = clock();int count = 0;for (unsigned long i = 2; i <= 10000; i++){if (isPrime(i)){cout << setw(4) << i << "\t";count++;if (count != 0 && count % 10 == 0){cout << endl;}}}endTime = clock();cout << "\nThe run time is " << static_cast<double>(endTime - startTime) / CLOCKS_PER_SEC<< "s." << endl;return 0;
}bool isPrime(unsigned long n)
{bool flag = true;unsigned long asquareRoot = static_cast<int>(sqrt(n)); // n的平方根for (int i = 2; i <= asquareRoot; i++){if (n % i == 0)flag = false;}return flag;
}

运行截图

代码运行时间0.19s,比b)中代码快了不少!
在这里插入图片描述

这篇关于C++大学教程(第九版)6.29素数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/634092

相关文章

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Maven的使用和配置国内源的保姆级教程

《Maven的使用和配置国内源的保姆级教程》Maven是⼀个项目管理工具,基于POM(ProjectObjectModel,项目对象模型)的概念,Maven可以通过一小段描述信息来管理项目的构建,报告... 目录1. 什么是Maven?2.创建⼀个Maven项目3.Maven 核心功能4.使用Maven H

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

Python虚拟环境终极(含PyCharm的使用教程)

《Python虚拟环境终极(含PyCharm的使用教程)》:本文主要介绍Python虚拟环境终极(含PyCharm的使用教程),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录一、为什么需要虚拟环境?二、虚拟环境创建方式对比三、命令行创建虚拟环境(venv)3.1 基础命令3

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve