C++统计10亿以内所有的质素(素数)的实现算法(附完整源码)

最新推荐文章于 2023-03-04 19:12:40 发布

源代码大师

最新推荐文章于 2023-03-04 19:12:40 发布

阅读量814

点赞数

分类专栏： C和C++算法完整教程 C和C++Everything教程

不予转载，严禁转载，违者必纠。

本文链接：https://blog.csdn.net/it_xiangqiang/article/details/114968362

版权

C和C++Everything教程同时被 2 个专栏收录

10029 篇文章 ¥99.90 ¥299.90

订阅专栏

超级会员免费看

C和C++算法完整教程

811 篇文章 ¥29.90 ¥99.00

订阅专栏

超级会员免费看

本文提供了C++编程语言中统计10亿以内所有质数（素数）的完整源码，包括算法定义、实现及main函数的测试部分。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

C++统计10亿以内所有的质素的实现算法

C++统计10亿以内所有的质素的实现算法完整源码（定义，实现，main函数测试）

C++统计10亿以内所有的质素的实现算法完整源码（定义，实现，main函数测试）

#include <cstring>
#include <iostream>

/** array to store the primes */
char prime[100000000];

/** Perform Sieve algorithm */

了解本专栏

订阅专栏解锁全文

超级会员免费看

确定要放弃本次机会？

福利倒计时

: :

立减 ¥

普通VIP年卡可用

立即使用

源代码大师

关注关注

0
点赞
踩
1

收藏

觉得还不错? 一键收藏
0
评论
分享

复制链接

分享到 QQ

分享到新浪微博

扫一扫
打赏
打赏
打赏举报

举报

专栏目录

订阅专栏

C++实现统计10亿以内所有质数的算法

LogicGuruX的博客

09-06

219

质数，也称为素数，是指大于1且只能被1和自身整除的正整数。在这篇文章中，我们将探讨如何使用C++编程语言来统计10亿以内所有的质数。该算法的基本思想是通过逐步筛选排除非质数，从而找出所有的质数。使用上述代码，我们可以在C++编程语言中实现高效地统计10亿以内所有质数的算法。该算法基于埃拉托斯特尼筛法，通过逐步筛选排除非质数，从而找出所有的质数。如果当前数值被标记为质数，那么将其所有的倍数标记为非质数。初始时，将所有的数值都标记为质数。的每个数值，输出所有被标记为质数的数值。，表示要统计质数的范围为10亿。

C++实现求解10亿以内所有质数的算法

最新发布

WangWEel的博客

08-22

295

该算法的时间复杂度为O(n*log(log(n)))，其中n为数组的大小。虽然该算法可以解决我们所提出的问题，但随着n的增大，其空间占用量也将增加，因此需要谨慎使用。最后，我们再次遍历整个数组，找到未被标记的元素，并输出它们作为质数。在本文中，我们将介绍一种使用C++编程语言实现的算法，用于计算10亿以内的所有质数。我们不仅会给出完整的源代码，还会提供相应的描述和解释，帮助您更好地理解这个算法的工作原理。循环遍历完整个数组，找到未被标记的元素，并将其视为一个质数。将数组中的所有元素初始化为true。

参与评论您还未登录，请先登录后发表或查看评论

使用lbaby筛，求10亿之内的所有素数（Yet Another Prime Algorithm)

飘零的思绪

04-22

2956

求10亿之内的所有素数原题目在这里：http://bbs2.chinaunix.net/thread-1433650-1-1.html1，第一步思考：只有个位数是 1 ,3 ,7 , 9 的数才可能是素数－－（结论1）根据这个结论，可以对 10亿内的自然数作如下划分：设集合G为：{ 个位数为1，3，7，9}集合X为:{个位数为 :0, 2, 4

素数筛法求十亿内所有质数的和（C++）

一串代码的博客

02-12

1158

筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数temp，这个数是素数，而temp的倍数可以直接筛掉。逐步迭代，可求出指定范围内的素数。public class Main { public static void main(String[] args) { Scanner in = new ...

c++笔记：秒解10亿以内素数及因式分解

chenmh82的博客

03-03

1742

最近在学c++，看到一种神奇的算法可以秒解10亿以内的所有素数，据说用了指针（还没学到，嘤），看不懂，姑且抄了下来，改吧改吧变成一个实现因式分解的程序 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;memory.h&amp;gt; #include&amp;lt;malloc.h&amp;gt; #include&amp;lt;iostre

十亿以内回文素数查找

11-19

十亿以内回文素数查找十亿以内回文素数查找十亿以内回文素数查找

C/C++编程小练习计算10亿之内的素数和(合数筛选算法实现)

lovemylife1234的博客

11-24

1508

计算10亿之内的素数和(合数筛选算法实现) 代码: #include #include #include #define MAX 1000000001 bool arr[MAX]; void filter(void); int main() { filter(); unsigned long long sum=2; long cnt=1; for(

2秒内计算10亿内素数筛法

08-18

最快的素数筛法, 2秒初始化后在奔腾4上能算出2^31 以内素数个数,之后10ms内算出任意 0-2^31之间素数个数，可快速的计算第k个素数, 枚举区间[n, m](m - n < 10^5)以内素数等还可以计算第k个数，分因素分解 Prime[78499] = 1000003 b ---------------------start benchmark------------------------ PI(2147483647) = 105097565, time use 232.64 ms k e8 -------------------start find kth prime--------------------- Prime[100000000] = 2038074743, time use 2.94 ms 10^7+100 e5-100 PI[10000100, 10100000] = 6239, time use 0.53 ms o 2^31+1 -------------------start factor prime---------------------- 2147483649 : 3 * 715827883 e9 PI(1000000000) = 50847534, time use 3.25 ms e10 e9 PI[10000000000, 11000000000] = 43336106, time use 1322.91 ms s e10 10 -------------------start print prime------------------------ PI[10000000000] = 455052511 0 prime number in range[10000000000, 10000000010] : s e10 100 -------------------start print prime------------------------ PI[10000000000] = 455052511 5 prime number in range[10000000000, 10000000100] : 10000000019 10000000033 10000000061 10000000069 10000000097

《ACM算法详解》— 求素数（质数）算法

69小石头的博客

05-02

1899

（不想做题了。。。。。整理一些资料吧）求素数（质数）算法如果一个正整数只有两个因子，1和p,则p为素数 1、根据概念判断 bool isPrime(int n) { if(n < 2) return false; for(int i = 2; i < n; ++i) if(n%i == 0) return false; r...

c语言找到10以内素数,C#求10以内所有素数的积

weixin_36356002的博客

05-20

1237

求1000000内的所有素数——C++实现

m0_56473031的博客

03-04

1224

信息安全数学基础编程作业题1-1——求1000000内的所有素数

求十亿内所有素数之和与个数

康宇的博客

09-21

626

求十亿内所有质数的和，怎么做最快? - PlanarG的回答 - 知乎 Min25筛实现，大约每100ms算一个 const int N = 1e6 + 10;//对应素数精度可以到1e10 typedef __int128 LL;//防止1e10 * 1e10爆long long namespace Min25 { int prime[N], id1[N], id2[N], flag[N], ncnt, m; LL g[N], sum[N], a[N], T, n; i

最快求素数的算法，求100000000以下素数0.3秒

08-05

最快求素数的算法，求100000000以下所有素数0.3秒，在10000000以下的数中找到664579个素数，耗时53毫秒

最快素数算法（绝非线性筛选）1.6秒算出1亿内所有素数

10-16

革命性素数算法:计算1亿内素数只要1.6秒算法基本跟之前发的C#版相同（http://download.csdn.net/source/690005内有算法描述），由我的朋友杨力2年前设计，时间复杂O(n)。我对其进行了革命性的数据结构改进，空间复杂度从2个O(n)降低到1/6个O(n)，程序的算法描述更加简洁，改用C++实现，我认为算法效率已经达到了素数算法的极限。注：创建的内存大小不要超过内存，否则效率下降

快速查找计算9百万万亿整数内全部素数（质数）的C++代码

ysh的博客

04-11

805

#编译测试环境：gcc version 9.2.0，在5.8.0-45-generic内核的linux试跑生成并验证了1亿以内的质数，通过以下代码查找到小于等于99999999的质数数量为5761455个，并与网上能查到的素数表，抽样检查过都是正确的。素数筛的原理啥的网上很多，就不讲了。由于计算long long型对应的最大整数9223372036854775807内的所有素质时，要用到动态数组，计算的数值越大，占用内存越大，请自行判断内存是否足够。直接贴代码： /* 功能：查找输出所有小于指

c++实现最快求质数个数以及质数的方法

会飞的大象的博客

03-27

3415

本博文利用了筛选法实现了质数的求取，并且利用数学分析的特性进行了代码优化，使得速度获得极大提升，不可多得 #include<iostream> #include<bitset> #include<cmath> #include<iostream> using namespace std; //最快的方法筛选法求质数 int main() { ...

输出一百,十万,一百万,一千万,一亿,十亿,二十亿以内的所有质数的方法,个数和优化后的运行时间对比

weixin_52785861的博客

01-18

5156

一共四个代码段首先是最基础的方法,因为方法效率太差,所以就用10W先进行测试,最终优化的程序将运行100W以内的所有质数,因为程序和人的思维计算能力不一样所以中间会有一个插曲,第三个和第四个代码的时候会说明. 第一个代码段是最基础的算法:输出10W以内的质数的数量和时间(同时本代码的结果用于对照优化后代码的输出正确性) 程序运行时间：7441ms 质数个数:9592 package cn.king; public class test1 { public static void main

目前已知的一种最快速的求素数的算法

corewolf0的专栏

05-16

1246

目前已知的一种最快速的求素数的算法就是Sieve of Atkin 算法！

期中作业参考-C++ OpenMP有限资源快速连续素数求取

丁劲犇技术发布空间

10-13

647

前面布置了求取素数的期中作业，各位同学都提交了答案。有筛法的，有直接两层for循环判断的。对于梅森素数，有快速算法，不过我们这次的要求是求取并输出连续素数表，能在规定时间内求取的越多越好。对筛法的连续求取程序，主要的问题是存储问题。筛法需要一个存储空间，用来存储标记。即使采用1bit这样的压缩存储，也是有上限的。尤其是学校的计算机内存只有2G。对简单的循环判断法，主要问题是时间开销，要注意对于N，只要验证sqrt(N)之内的素数能否整除N即可，而不是采用暴力的两层for ++ 我把曹景焕同学的程序略加修

C++编程基础：1000内素数与经典算法实现源码解析

标题“基础问题C++源码(初学必备)”和描述“包含1000内素数、最大公约数、字符串倒置、输出杨辉三角、斐波那契数列、倒序排数等等基础问题求解的C++源码”共同指向了C++编程学习中的一些基础算法和编程技巧。...