C语言求一个大数范围以内的素数(质数)既然如此简单

article/2025/7/5 4:16:43

⭐本章简介

本章讲解一下C语言求素数的一个程序。5种求解方式,最后一种可以求大数!
有多种方法,难度依次增大(但是不会太大),程序的质量也依次增大。

♾️目录

  • ⭐本章简介
  • ⭐求素数的方法
    • 💡暴力求解
    • 💡优化后的暴力求解
    • 💡标记求解
    • 💡封装成对象
    • 💡利用 Bitmap 求解大数素数
  • 👋都看到这里了,还不快点个关注?

⭐求素数的方法

💡暴力求解

通过遍历除1以外小于欲求质数 x 的所有整数,如果有一个数可以被x整除。那么x就不是质数。

#include <stdio.h>// 输入数 x 如果 x 是素数 就返回 true 否则就返回 false
bool IsPrimeNumber( int x );int main(){int a=1,b=100;for( int i = a ; i <= b ; i++ ){// 如果他是素数就打印出来if( IsPrimeNumber(i) ){printf("%d  ",i);} else { }}}bool IsPrimeNumber( int x ){// 遍历除 1 以外所有比自己小的整数for( int i = x - 1 ; i > 1 ; i-- ){if( x%i == 0 ){// 如果 x 可以被 i 整除 那么就返回的 假 代表这个数不是素数return false;} else { /* 如果不能被 i 整除就继续遍历 */ }}// 如果除 1 以外所有比自己小的整数都不能被整除,那么他就是素数if( x <= 1 ){return false;} else {return true;}
}

这种方法有个特点 当 x 越大,那么 IsPrimeNumber 函数的运算时间也就越长。如果要求 一到100001以内的所有质数,要求好久才可以求得。
暴力求解
暴力求解 9w10w 以内的素数包括控制台输出时间费时2.699s

💡优化后的暴力求解

如果 1 到 x 以 内 的 整 数 \color{red}{1 到 \sqrt{x}}以内的整数 1x 均不能被 x 整除。那么后面就不可能有数被 x 整除 。这是因为如果 1 到 x 1 到 \sqrt{x} 1x 以内的数可以被整除的话,那么除出的结果一定是大于 x \sqrt{x} x 的。

#include <stdio.h>
#include <math.h>// 输入数 x 如果 x 是素数 就返回 true 否则就返回 false
bool IsPrimeNumber( int x );int main(){// 求 集合 [a,b] 中的所有素数int a=0,b=100;for( int i = a ; i <= b ; i++ ){// 如果他是素数就打印出来if( IsPrimeNumber(i) ){printf("%d  ",i);} else { }}}bool IsPrimeNumber( int x ){// 遍历除 1 以外所有比自己小的整数int sq = sqrt(x);for( int i = 2 ; i <= sq; i++ ){if( x%i == 0 ){// 如果 x 可以被 i 整除 那么就返回的 假 代表这个数不是素数return false;} else { /* 如果不能被 i 整除就继续遍历 */ }}// 如果除 1 以外所有比自己小的整数都不能被整除,那么他就是素数if( x <= 1 ){return false;} else {return true;}
}

这个方法比起暴力求解的计算时间久减少了很多。暴力求解需要的时间是t的话,那么这个方法求解的时间 大约就是 t \color{red}\sqrt{t} t 时间减少了很多。
优化后的暴力求解
优化后的暴力求解求 111w 包括控制台输出时间废时 2.813s

💡标记求解

利用一下两条定理:

  • 所有素数的倍数都不是素数
  • 非素数一定有一个约数是素数;
    这样子我们就可以定义一个列表 [0,n] 每求出一个素数x就把这个列表中所有x的倍数都去标记成非素数。那么没有标记的就是素数。又因为我们知道最小的素数是2,所以我们就从2开始标记起。
    而且有 优化后的暴力求解 可以知道,我们只要求出 [0, n \sqrt{n} n ] 以内的素数的时候排除掉所有素数的倍数,就可以排除掉 [0,n] 以内的所有素数了。
#include <stdio.h>
#include <math.h>// 输入数 x 如果 x 是素数 就返回 true 否则就返回 false
bool IsPrimeNumber( bool *list , int x );
// 把 x 标志成素数
void SetPN( bool *list , int x );
// 把 x 标志成非素数
void ResPN( bool *list , int x );
// 把 list 中的素数标记出来
void GetPrimeNumber( bool *list , int b );int main(){int a=90000,b=100000;//定义一个列表 为了方便 如果是 0 就是素数 不是 0 就不是素数bool list[1000000] = {1,1,0};// 循环遍历  [0,sqrt(n)] GetPrimeNumber(list,b);for( int i = a ; i <= b ; i++){if( IsPrimeNumber(list,i) ){printf("%d ",i);} else { }}}void GetPrimeNumber( bool *list , int b ){for( int i = 2 ; i <= sqrt(b) ; i ++ ){// 如果 i 是素数的话 if( IsPrimeNumber( list  , i ) ){// 去除列表内 i 的倍数for( int j = 2 ;  ; j++ ){// 如果 i * j 超出需要求的列表范围就退出if( i*j > b ){break;}ResPN(list,i*j);}}}
}bool IsPrimeNumber( bool *list  ,int x ){if(list[x]){return false;} else {return true;}
}void SetPN( bool *list , int x ){list[x] = false;
}void ResPN( bool *list , int x ){list[x] = true;
}

一定要注意 列表长度一定要远 要大于 b 否则容易出现意想不到的结果 ,这种求法实际上已经把 [0,n] 以内的所有质素求出来了。不仅仅是 [a,b]。
在这里插入图片描述

💡封装成对象

我们可以把 标记求解 封装成对象

#include <stdio.h>
#include <math.h>class PrimeNumber {bool list[1000000] = {1,1,0};public:void GetPrimeNumber( int b ){for( int i = 2 ; i <= sqrt(b) ; i ++ ){// 如果 i 是素数的话 if( IsPrimeNumber( i ) ){// 去除列表内 i 的倍数for( int j = 2 ;  ; j++ ){// 如果 i * j 超出需要求的列表范围就退出if( i*j > b ){break;}ResPN(i*j);}}}}bool IsPrimeNumber( int x ){if(list[x]){return false;} else {return true;}}private:void SetPN( int x ){list[x] = false;}void ResPN( int x ){list[x] = true;}
};int main(){int a=90000,b=100000;//定义一个列表 为了方便 如果是 0 就是素数 不是 0 就不是素数PrimeNumber p;// 循环遍历  [0,sqrt(n)] p.GetPrimeNumber(b);for( int i = a ; i <= b ; i++){if( p.IsPrimeNumber(i) ){printf("%d ",i);} else { }}
}

💡利用 Bitmap 求解大数素数

虽然利用Bitmap会增大计算量,但是利用上面的技巧求解速度已经非常快了。利用BitMap可以求解大数的素数列表。

#include <stdio.h>
#include <math.h>class PrimeNumber {unsigned char list[2000000] = {3};public:void GetPrimeNumber( unsigned int b ){for( unsigned int i = 2 ; i * i  <= b ; i ++ ){// 如果 i 是素数的话 if( IsPrimeNumber( i ) ){// 去除列表内 i 的倍数for( unsigned int j = 2 ;  ; j++ ){// 如果 i * j 超出需要求的列表范围就退出if( i*j > b ){break;}ResPN(i*j);}}}}bool IsPrimeNumber( int x ){if(Get_bit(list,x)){return false;} else {return true;}}private:void SetPN( int x ){Res_bit(list,x);}void ResPN( int x ){Set_bit(list,x);}bool Get_bit( unsigned char * st , unsigned int num ){return ( st[(int)(num/8)] & (0x01 << (num % 8) ) ) > 0 ? true : false ;}void Set_bit( unsigned char * st , unsigned int num ){st[(int)(num/8)] |= (0x01 << (num % 8) ) ;}void Res_bit( unsigned char * st , unsigned int num ){st[(int)(num/8)] &= ~(0x01 << (num % 8) ) ;}};int main(){unsigned int a=13999000,b=14000000;//定义一个列表 为了方便 如果是 0 就是素数 不是 0 就不是素数PrimeNumber p;// 循环遍历  [0,sqrt(n)] p.GetPrimeNumber(b);for( unsigned int i = a ; i <= b ; i++){if( p.IsPrimeNumber(i) ){printf("%d ",i);} else { }}
}

下面是求解 13,999,000 一千三百九十九万九千14,000,000 一千四百万 的素数列表 。
利用Bitmap求解大数素数


13999003 13999009 13999057 13999079 13999099 13999121 13999133 13999147 13999159 13999169 13999171 13999189 13999213 13999253 13999267 13999273 13999289 13999291 13999301 13999309 13999351 13999369 13999393 13999397 13999399 13999421 13999423 13999441 13999459 13999463 13999471 13999477 13999481 13999519 13999529 13999537 13999549 13999597 13999603 13999621 13999651 13999673 13999691 13999703 13999723 13999729 13999747 13999757 13999759 13999781 13999787 13999813 13999831 13999871 13999873 13999877 13999889 13999919 13999957 13999961 13999969 13999981


如果不了解BitMap想了解的可以进我主页搜索BitMap。

👋都看到这里了,还不快点个关注?


✍️本文作者为 > 【谢玄.】 Mr-XieXuan < 于 2022/10/28/3:00 发布于 CSDN 。

📧E-mail: [ Mr_Xie_@outlook.com ]
⌨️GitHub: [ https://github.com/MR-XieXuan }
🔍个人私站: [ https://main.mrxie.xyz/ ]


http://chatgpt.dhexx.cn/article/XCYKtHPZ.shtml

相关文章

判断素数、输出100内素数 C语言初学

素数又称质数。所谓素数是指除了 1 和它本身以外&#xff0c;不能被任何整数整除的数&#xff0c;例如13就是素数&#xff0c;因为它不能被 2~12 的任一整数整除。 判断一个整数m是否是素数&#xff0c;只需把 m 被 2 ~ m-1 之间的每一个整数去除&#xff0c;如果都不能被整除&…

C语言:查找打印质数(素数)

这个题是很灵活的&#xff0c;有几种解法&#xff0c;也有很多种优化方法&#xff0c;这里&#xff0c;我来谈谈一种个人感觉比较容易理解的方法。 首先&#xff0c;要知道质数&#xff08;素数&#xff09;是什么&#xff1f; 质数&#xff08;素数&#xff09;是除了1和它本…

输出100 - 200之间的素数C语言

输出100 - 200之间的素数 素数就是质数&#xff0c;即除了1和它本身不再有求它因数的自然数 那么这道题的思路就是用100到200之间的数去除以比这个数小的所有数&#xff08;除了1和它本身&#xff09;&#xff0c;如果有余数说明它不是一个素数 看下面代码&#xff1a; int m…

求素数C语言

求素数C语言 代码如下&#xff1a; #include<stdio.h> int main() {int i, n;printf("请输入一个数:"); scanf("%d", &n);for (i 2; i < n ; i){if (n%i 0)break;}if (n <1 ) printf("这不是素数\n");else if (i < n) pr…

QQ群 该页面暂时无法显示

如图&#xff0c;在使用QQ群文件时出现“该页面暂时无法显示”的错误信息。 首先检查IE能否正常使用。 打开IE果然显示了错误信息&#xff0c;按照说明改正代理服务器信息。QQ群即可正常使用。

qq群文件问题完美解决

1.点开设置 2.点击网络和Internet 3.点击网络和共享中心 4.点击你家的WiFi 5.点击属性 6.把这个前面的对勾取消掉 7.点击确定 8.完成操作

解决QQ或TIM下载群文件网路失败或者网速贼慢的办法

这几天项目上有些文件都放在了Q群上&#xff0c;可是发现只要稍微大一点的文件基本都是下载失败&#xff0c;不是网络错误就是下载半天才下好&#xff0c;现在介绍一下解决的办法&#xff1a; 1- 百度上搜索“群空间” 2- 登录你的QQ账号 3- 在右上角有我的QQ群&#xff0c;在…

解决PC端的的TIM群聊界面无法显示公告、文件、记录栏,不显示群消息

笔者的PC端TIM经常遇到各种“暂时无法显示”&#xff0c;公告、文件、记录栏&#xff0c;群消息都没了。 解决方法&#xff1a; 打开ie浏览器右上角齿轮->Internet选项->连接->局域网设置只勾选 自动检测设置把代理关了。 就能正常显示 转载自贴吧草上黑

电脑版QQ或TIM群文件无法显示,空白,加载不出来

问题描述 登陆电脑版QQ或者TIM后&#xff0c;点击群文件&#xff0c;显示无法打开。 解决办法 将代理服务器关闭&#xff0c;然后QQ或者TIM群文件就能打开啦。&#xff08;然后代理服务器自己确定是否再次开启&#xff09; 参考博文 参考博文1

QQ “安全检查未通过,禁止下载该文件” 解决方法

经评论区提醒&#xff0c;此方法可能已经不再适用。如有人成功解决了&#xff0c;或者没有成功解决&#xff0c;麻烦评论区告诉我一下。谢谢&#xff01; 在下载群文件的时候&#xff0c;偶尔会遇到上图的情况&#xff0c;明明是正经文件&#xff0c;却没有通过安全检查。解决方…

解决QQ群、讨论组上传文件,由于网络原因上传失败?

最近qq上传群文件老是失败&#xff0c;但是同事他们可以&#xff0c;目前已经解决QQ群、讨论组上传文件&#xff0c;由于网络原因上传失败&#xff1f;&#xff0c;做法如下&#xff1a; 输入regedit&#xff0c;打开注册表&#xff0c;然后找到这个位置HKEY_CURRENT_USER\Sof…

QQ头像无法加载,显示初始默认头像的解决方法

前言 终于。。终于&#xff01;查过那么多资料&#xff0c;翻过无数带有蛛丝马迹的信息&#xff0c;根本没有人能解决我遇到的这个问题&#xff0c;它是如此独特&#xff0c;如此难以排查&#xff01;&#xff01; 删过文件、改过网络配置、本地测试过相关数据接口、重装过QQ、…

安全检查未通过_QQ群文件未通过安全检查,禁止下载该文件解决办法(QQ收藏)

需要从群文件下载一个压缩包文件,可是却显示下载失败,具体原因为“QQ群文件未通过安全检查,禁止下载该文件”,按有的说法在设置里把安全防护的等级设置为最低,还是不行,手机也同样。 在将放弃的时候,发现直接用手机收藏群文件,然后用电脑登上qq去收藏里面下载完美解决。…

QQ群无法下载视频和图片解决方案

最近换的新电脑 登录QQ后发现在QQ群里的图片或视频无法下载 如图所示&#xff1a; 一开始以为还是 网络问题 导致无法下载 但是 不影响聊天和上传文件 &#xff1f;&#xff1f;&#xff1f; 意味着网络正常 想了下 新电脑 外置的硬盘一直未装 下载的路径改变了 重新定义的本…

【问题记录】qq中群文件、群相册以及一些服务一直显示不出来

一、问题描述 qq各种服务不给力&#xff0c;以为是qq设置的原因&#xff0c;卸载后重装还是不行 二、解决方法 问了度娘&#xff0c;试了又试&#xff0c;最后通过去掉代理服务器成功解决了问题&#xff0c;步骤如下&#xff1a; 1.按下WinR组合bai键打开运行&#xff0c;…

QQ群文件无法正常显示/微信(PC)电脑端公众号文章打开后显示一片空白的解决办法

QQ群文件无法正常显示/微信&#xff08;PC&#xff09;电脑端公众号文章打开后显示一片空白的解决办法&#xff1a; 【解决办法】 1.打开ie浏览器&#xff0c;右上角类似齿轮的图标&#xff0c;找到Internet选项&#xff0c;打开 2.找到局域网设置 3.把下图中的所有钩去掉 4.…

QQ出现“该页面暂时无法显示”解决办法!

1 问题 电脑QQ/TIM不知道怎么回事除了消息界面&#xff0c;其他文件&#xff0c;公告&#xff0c;设置都无法打开。 2 原因 时很有可能你电脑自带的&#xff0c;或者你电脑中的IE浏览器也是无法正常使用&#xff0c;因为QQ群使用的是IE的内核。 3 解决 -----首先检查IE能否…

电脑无法正常上网以及QQ群文件一直显示刷新

电脑无法正常上网以及QQ群文件一直显示刷新 不知道是因为使用了VPN还是什么原因&#xff0c;反正电脑突然就出现了能上网又不能不上网的状态。 就是电脑的wifi显示已连接&#xff0c;但是无法访问网页&#xff0c;QQ能登陆但是群文件以及除了聊天框其他地方基本都是显示页面无…

python 下载qq群文件,QQ群文件下载失败怎么办?解决QQ群文件下载失败的解决方法...

QQ群分享文件无法下载的问题很烦人&#xff0c;具体原因涉及到系统控件加载&#xff0c;防火墙&#xff0c;IE设置&#xff0c;internet选项等等&#xff0c;如果慢慢去排除花时间&#xff0c;麻烦&#xff0c;也不能解决。重装软件也不能解决问题&#xff0c;重装系统更是扯淡…

服务器保存qq群聊天图片无法显示,电脑中qq群聊天图片无法查看的解决方法

一位用户反馈自己在电脑中使用QQ聊天时&#xff0c;经常看不到别人发送的图片&#xff0c;只能看到图片缓冲的样子&#xff0c;这是怎么回事呢&#xff1f;接下来&#xff0c;系统城小编就为大家分享电脑中qq群聊天图片无法查看问题的解决方法。 方法如下&#xff1a; 1、首先&…