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

相关文章

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

Linux卸载自带jdk并安装新jdk版本的图文教程

《Linux卸载自带jdk并安装新jdk版本的图文教程》在Linux系统中,有时需要卸载预装的OpenJDK并安装特定版本的JDK,例如JDK1.8,所以本文给大家详细介绍了Linux卸载自带jdk并... 目录Ⅰ、卸载自带jdkⅡ、安装新版jdkⅠ、卸载自带jdk1、输入命令查看旧jdkrpm -qa

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

MySQL Workbench 安装教程(保姆级)

《MySQLWorkbench安装教程(保姆级)》MySQLWorkbench是一款强大的数据库设计和管理工具,本文主要介绍了MySQLWorkbench安装教程,文中通过图文介绍的非常详细,对大... 目录前言:详细步骤:一、检查安装的数据库版本二、在官网下载对应的mysql Workbench版本,要是

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Linux安装MySQL的教程

《Linux安装MySQL的教程》:本文主要介绍Linux安装MySQL的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux安装mysql1.Mysql官网2.我的存放路径3.解压mysql文件到当前目录4.重命名一下5.创建mysql用户组和用户并修

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque