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

相关文章

2025版mysql8.0.41 winx64 手动安装详细教程

《2025版mysql8.0.41winx64手动安装详细教程》本文指导Windows系统下MySQL安装配置,包含解压、设置环境变量、my.ini配置、初始化密码获取、服务安装与手动启动等步骤,... 目录一、下载安装包二、配置环境变量三、安装配置四、启动 mysql 服务,修改密码一、下载安装包安装地

电脑提示d3dx11_43.dll缺失怎么办? DLL文件丢失的多种修复教程

《电脑提示d3dx11_43.dll缺失怎么办?DLL文件丢失的多种修复教程》在使用电脑玩游戏或运行某些图形处理软件时,有时会遇到系统提示“d3dx11_43.dll缺失”的错误,下面我们就来分享超... 在计算机使用过程中,我们可能会遇到一些错误提示,其中之一就是缺失某个dll文件。其中,d3dx11_4

Linux下在线安装启动VNC教程

《Linux下在线安装启动VNC教程》本文指导在CentOS7上在线安装VNC,包含安装、配置密码、启动/停止、清理重启步骤及注意事项,强调需安装VNC桌面以避免黑屏,并解决端口冲突和目录权限问题... 目录描述安装VNC安装 VNC 桌面可能遇到的问题总结描js述linux中的VNC就类似于Window

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

Go语言编译环境设置教程

《Go语言编译环境设置教程》Go语言支持高并发(goroutine)、自动垃圾回收,编译为跨平台二进制文件,云原生兼容且社区活跃,开发便捷,内置测试与vet工具辅助检测错误,依赖模块化管理,提升开发效... 目录Go语言优势下载 Go  配置编译环境配置 GOPROXYIDE 设置(VS Code)一些基本

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

Java JDK1.8 安装和环境配置教程详解

《JavaJDK1.8安装和环境配置教程详解》文章简要介绍了JDK1.8的安装流程,包括官网下载对应系统版本、安装时选择非系统盘路径、配置JAVA_HOME、CLASSPATH和Path环境变量,... 目录1.下载JDK2.安装JDK3.配置环境变量4.检验JDK官网下载地址:Java Downloads

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被