c语言正整数分为素数乘积,c语言:实现对于给定的正整数N,依次打印出小于等于N的所有素数。两种方法及其优化..._韩睿芝的博客-程序员宅基地

技术标签: c语言正整数分为素数乘积  

请编写一个程序,实现对于给定的正整数N,依次打印出小于等于N的所有素数。

方法一:试除法

由素数的定义得到如下程序:

#include

int print_prime(int num)//prime表示素数

{

int i = 0;

for (i = 2; i <= num; i++)

{

int j = 0;

for (j = 2; j < i; j++)

{

if (i%j == 0)

{

break;

}

}

if (i==j)

{

printf("%d\t",i);

}

}

}

int main()

{

int num;

printf("请输入一个正整数:");

scanf("%d", &num);

if (num > 1)

{

printf("打印出所有的素数:");

print_prime(num);

}

else

{

printf("不存在小于等于%d的素数", num);

}

printf("\n");

return 0;

}

上面的代码中,在判断素数时一直从2试除到n-1。这里从n/2之后的数到n-1的试除显然是多余的,比如正整数7不能被2整除,必然不能被4,6整除。

优化1:

试除的范围优化到[2,n/2],则工作量减少一半,代码如下:

int print_prime(int num)//prime表示素数

{

int i = 0;

for (i = 2; i <= num; i++)

{

int j = 0;

for (j = 2; j <= i/2; j++)//修改部分

{

if (i%j == 0)

{

break;

}

}

if (j == (i/2+1))//修改部分

{

printf("%d\t", i);

}

}

}

既然能将试除范围优化到[2,n/2],那么这个范围是不是还能继续优化呢?答案是肯定的,在[2,n/2]这个范围里(√n,n/2]的试除也是多余的。因为因数是成对出现的,如16可分解为:1和16 、2和8、4和4、8和2、16和1。这些因数里必然有一个小于等于4。故只需试除小于等于√n的数就可以了。

优化2:

试除范围优化为[2,√n],代码如下:

#include

#include//修改部分

int print_prime(int num)//prime表示素数

{

int i = 0;

for (i = 2; i <= num; i++)

{

int j = 0;

for (j = 2; j <=sqrt(i); j++)//修改部分

{

if (i%j == 0)

{

break;

}

}

if (j > sqrt(i))//修改部分

{

printf("%d\t", i);

}

}

}

上面所有的代码在找素数的时候是从2到n,在这个范围内除了2之外的偶数都不是素数,所以可以跳过这些偶数。

还有试除范围内除了2之外的偶数也是没有必要的,因为如果不能被2整除,必然不能被大于2的偶数整除。

优化3:

寻找素数时和试除范围内跳过除2之外的偶数。代码如下:

int print_prime(int num)//prime表示素数

{

int i = 0;

printf("%d\t", 2);//修改部分

for (i = 3; i <= num; i+=2)//修改部分

{

int j = 2;

for (j = 3; j <= sqrt(i); j+=2)//修改部分

{

if (i%j == 0)

{

break;

}

}

if (j > sqrt(i))

{

printf("%d\t", i);

}

}

}

在上面的代码中,试除范围内的一些数也是不必要的。比如判断101是否为素数时,要分别试除小于10的2和所有奇数,即2、3、5、7、9,其中对9的试除是不必要的。即对所有的非素数的试除是不必要的,因为非素数必然可分解为比它小的素数的乘积,既然它的质因数不能整除某个数,这个数必然也不能。故试除的范围可缩小到小于等于√n的所有素数。

优化4:

只试小于√n的素数,那么问题来了,要试除这些素数时必然要将前面求出的素数保存起来,开辟多大一块空间合适呢?因为n的大小未知,所以无法确定开辟多少空间。这里暂时没有完全解决的办法,我的做法是先开辟大小为1000的空间,需要时再修改。

#include

#include

#define MAX 1000  //定义数组的大小

int print_prime(int num)//prime表示素数

{

int arr[MAX] = { 0 };

int i = 0,j=1;

printf("%d\t", 2);

arr[0] = 2;

for (i = 3; i <= num; i += 2)

{

int k = 0;

while (arr[k]>0&&arr[k]<=sqrt(i))

{

if (i%arr[k] == 0)

{

break;

}

k++;

}

if (!arr[k]||(arr[k] > sqrt(i)))

{

printf("%d\t", i);

arr[j] = i;

j++;

}

}

}

int main()

{

int num;

printf("请输入一个正整数:");

scanf("%d",&num);

if (num > 1)

{

printf("打印出所有的素数:");

print_prime(num);

}

else

{

printf("不存在小于等于%d的素数",num);

}

printf("\n");

return 0;

}

方法二:筛选法

这种方法求素数的思想就是,不断筛去最小的数的倍数。这个最小的数必然是素数。

比如最小的素数是2,去掉所有2的倍数;接下来最小的数是3,3就是素数,去掉所有的3的倍数;依次类推,直到最小的数小于等于√n为止。为什么是√n呢? 在上面的试除法中讲到只要试除小于等于√n的所有素数即可判断出小于等于n的所有素数,这里同样适用,只要去掉所有的小于等于√n的所有数的倍数,剩下的数就是小于等于n的所有素数。

代码如下:

#include

#include

#define MAX 1000  //定义数组的大小

int print_prime(int num)//prime表示素数

{

int arr[MAX] ;

int i = 0,j=0;

for (i = 0; i < num - 2; i++)//初始化数组[2,num]

{

arr[i] = i + 2;

}

while (arr[j]<=sqrt(num))//除数的范围

{

for (i = j + 1; i < num - 1; i++)

{

if (arr[i]%arr[j] ==0)//筛去arr[i]的倍数

{

arr[i] = 0;

}

}

j++;

while(!arr[j])//确定最小数

{

j++;

}

}

for (i = 0; i < num - 1; i++)

{

if (arr[i])

{

printf("%d\t",arr[i]);

}

}

}

int main()

{

int num;

printf("请输入一个正整数:");

scanf("%d",&num);

if (num > 1)

{

printf("打印出所有的素数:");

print_prime(num);

}

else

{

printf("不存在小于等于%d的素数",num);

}

printf("\n");

return 0;

}

上面的代码有一个很明显的缺陷就是开辟空间过大,如何来解决这个问题呢?

上述代码所开辟的空间为int型,占用4个字节,占用空间太多,可以构造一个bool型数组,bool型是一个基本的数据类型,占1个字节,以下标来存储数据,节省了75%的空间。

优化:

构造bool型数组,以下标来存储数据,每个数只占一个字节。

代码如下:

#include

#include

#include

#define MAX 1000  //定义数组的大小

void print_prime(int num)//prime表示素数

{

bool arr[MAX] ;

int i = 0,j=2;

for (i = 0; i

{

arr[i] = 1;

}

while (arr[j]<=sqrt(num))//除数的范围

{

for (i = j + 1; i <= num ; i++)

{

if (i%j ==0)//筛去arr[i]的倍数

{

arr[i] = 0;

}

}

j++;

while(!arr[j])//确定最小数

{

j++;

}

}

for (i = 2; i <=num ; i++)//打印素数

{

if (arr[i])

{

printf("%d\t",i);

}

}

}

int main()

{

int num;

printf("请输入一个正整数:");

scanf("%d",&num);

if (num > 1)

{

printf("打印出所有的素数:");

print_prime(num);

}

else

{

printf("不存在小于等于%d的素数",num);

}

printf("\n");

return 0;

}

结果1:

请输入一个正整数:9

打印出所有的素数:2     3       5       7

请按任意键继续. . .

结果2:

请输入一个正整数:1

不存在小于等于1的素数

请按任意键继续. . .

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_32108979/article/details/117081789

智能推荐

测试java微服务_Java微服务应用测试,走起_咪马3213�m~~的博客-程序员宅基地

从近几年的技术发展来看,行业里提到微服务应用场景越来越多,是时候能够提升目前的业务扩展能力了。相比于传统的EJB,SOA的方案,微服务是一种相对于更加轻量的方案,在Java领域有很多种实现,spring cloud算是一种,还有比如dubbo等等。我们就简单演示下如何通过idea的工具来创建一个简单的微服务应用,以此为切入点,我们会牵扯出整个微服务的额整体设计,来尽可能达到融会贯通的的。我们创建...

java获取当地天气_java获取天气预报的信息_胡钥的博客-程序员宅基地

运行效果:主要功能:1,jsp页面输入省份和城市 根据条件获取当地的天气信息2,java代码 利用第三方的省份和城市的路径地址本工程主要实现java获取天气预报的信息步骤1,创建工程weatherDemo2,创建包结构3,创建类4,访问第三方接口 打开主机方法5,获取省份id方法6,获取市id方法7,获取天气的方法8,编写servlet9,发布运行java代码创建WeatherDemo类/*** ...

Keras使用预网络学习,迁移学习,特征提取,数据增强 VGG16_Arthur-Ji的博客-程序员宅基地

代码from keras.applications import VGG16train_dir = os.path.join(base_dir, 'train')conv_base = VGG16(weights='imagenet', include_top=False, input_shape=(150, 150...

oracle索引降低并行度,分区索引的并行度_阿尔法小分队的博客-程序员宅基地

今天被一个小女同事问一个问题,索引的可以通过 dba_indexes.degree查看,子分区索引的并行度是怎么查看的?应该是目前还没有这个东西。SQL&gt; conn song/songConnected.SQL&gt; CREATE TABLE t_par2 (id number,name varchar2(10))3 PARTITION BY range (id)4 ( ...

linux 查看mysql 负载_Linux系统负载过高排查检测命令_观察君的博客-程序员宅基地

Linux系统负载过高排查检测命令发布时间:2020-9-10 14:32:04浏览量:421【字体:大 中 小】//查看磁盘IO情况;(安装命令 yum install -y sysstat)[[email protected] ~]# iostat -d -m 1 10Linux 4.18.0-193.14.2.el8_2.x86_64 (zabbix5) 09/09/2020...

多字段mysql触发器实例_MySQL通过触发器解决数据库中表的行数限制详解及实例..._地下室的光的博客-程序员宅基地

MySQL通过触发器解决数据库中表的行数限制详解及实例最近项目一个需求是对操作日志的数量限制为10万条,超过十万条便删除最旧的那一条,保存数据库中日志数量不超过10万。当时我的第一想法是通过触发器来做,便在数据库中执行了如下的SQL:?delimiter $create trigger limitLogbeforeinserton OperationLogfor each rowbeginif (...

随便推点

我的世界服务器修改速度,我的世界运算变速 TickrateChanger mod_兔纸周嬷嬷的博客-程序员宅基地

我的世界运算变速 TickrateChanger mod,这款模组可以控制游戏内的时间流动的,让一切都变快,就像上帝拨动了时间的时钟一样,当时间加速的时候,你可以看见游戏内的各种生物都在快速的生长和移动,时间变慢时,则所有的物体都在变慢。我的世界运算变速 TickrateChanger mod介绍我的世界运算变速 TickrateChanger mod这款模组使你有可能改变游戏的速度。你可以使用这...

java 操作系统 模拟 daima_编写一个程序,利用Java语言模拟操作系统进程调度管理..._weixin_39689506的博客-程序员宅基地

该楼层疑似违规已被系统折叠隐藏此楼查看此楼import java.util.PriorityQueue;public class Process implements Comparable {private String name;private int priority;public Process(String name, int priority) {this.name = name;th...

mysql数据库报错203_远程连接mysql数据库时报错: 错误代码 2003不能连接到MySQL服务器在*.*.*.*(111)..._麦读的博客-程序员宅基地

在测试服务器上安装完mysql后, 服务器自己访问没有问题, 但是本地通过sql客户端连接时报错:错误代码 2003不能连接到MySQL服务器在*.*.*.*(111)。在网上查了一些资料,解决方案有:1.关闭防火墙2.数据库中修改用户的访问权限3./etc/my.cnf中将bind-address属性注释掉三种方案我都试了,但还是不行,通过netstat -an | grep 3306 命令...

java中描述多态的特点_理解java的三大特性之多态_投研双杰的博客-程序员宅基地

面向对象编程有三大特性:封装、继承、多态。封装隐藏了类的内部实现机制,可以在不影响使用的情况下改变类的内部结构,同时也保护了数据。对外界而已它的内部细节是隐藏的,暴露给外界的只是它的访问方法。继承是为了重用父类代码。两个类若存在IS-A的关系就可以使用继承。,同时继承也为实现多态做了铺垫。那么什么是多态呢?多态的实现机制又是什么?请看我一一为你揭开:所谓多态就是指程序中定义的引用变量所指向的具体类...

iOS14 UIWebView_diab16244的博客-程序员宅基地

显示网页数据代理方法&lt;UIWebViewDelegate&gt;shouldStartLoadWithRequest: 请求之前判断是否允许访问(过滤某些网址)属性UIScrollView可以控制滚动范围loadHTMLStringloadData:可以加载网络资源和本地资源scalesPageToFit 屏幕自适应dataDetectorTyp...

8192游戏C语言源代码,粤嵌arm开发版2048小游戏c语言代码_I6and7的博客-程序员宅基地

#include #define UP 1#define DOWN 2#define LEFT 3#define RIGHT 4int *plcd = NULL;char *bmp_name[] ={"color_x80_2.bmp","color_x80_4.bmp","color_x80_8.bmp","color_x80_16.bmp","color_x80_32.bmp","color_x...

推荐文章

热门文章

相关标签