`
rokuan
  • 浏览: 20406 次
  • 性别: Icon_minigender_1
  • 来自: 苏州
社区版块
存档分类
最新评论

筛减法求素数

阅读更多
这种方法的求素数的效率很高
#include <stdio.h>
#include <stdlib.h> 

/*筛选法求素数,即质数 
	素数是只能被1和自身整除的数 
	从2开始递增,删除此数的倍数,则以后出现的就都是素数了 
*/

int main(int argc, char *argv[])
{
	//atoi函数将字符串转化为长整型 
	int i, j, N = atoi(argv[1]);
	int *a = malloc(N * sizeof(int)); 
	//初始化 
	for (i = 0; i < N; i++)	a[i] = 1;
	for (i = 2; i < N; i++)
		if (a[i])
			for (j = i; j <= N/i; j++)	a[i*j] = 0;
	for (i = 2; i < N; i++)
		if (a[i])	printf("%4d ", i);
	printf("\n");
} 

执行如下:


  • 大小: 8.8 KB
分享到:
评论

相关推荐

    c语言用数组实现求素数,并且运算过程仅使用+-法

    ### C语言用数组实现求素数,并且运算过程仅使用+-法 #### 概述 在计算机科学领域,素数的检测与生成是一项常见的任务,尤其是在加密算法、数学建模等场景中。本文将详细解释如何使用C语言通过数组来找出一定范围...

    素数环 回溯法——C语言代码

    在素数环中,每个素数都可以通过加法或减法与相邻的素数组成等差数列。例如,4、6、2就形成一个素数环,因为4+2=6,6-2=4。寻找素数环是探索数论性质的一种方式,同时也是一种算法挑战。 在本项目中,我们将使用...

    素数环原代码(加注释)

    素数环是指一个由素数组成的环,其中每个素数都可以通过加法或减法与环中的另一个素数形成连续的素数链。例如,4,6,2,3构成一个素数环,因为4-2=2, 6-4=2, 6+3=9(不是素数),但3+6=9,9-2=7(是素数),7-3=4,形成了...

    大数计算(运算)器(支持大素数判定和大数阶乘)

    为了判断一个大数是否为素数,可以使用多种方法,如试除法、埃拉托斯特尼筛法、米勒-拉宾素性检验等。对于大数,米勒-拉宾测试是一种实用的算法,它基于概率理论,虽然不能保证绝对正确,但可以通过多次测试提高准确...

    大数运算+ - * / 和素数检测等

    更高效的算法有埃拉托斯特尼筛法,用于找出一定范围内所有素数,但它并不适用于单个数字的素数检测。另一种是米勒-拉宾素数检验,这是一种概率性测试,能够快速判断一个大数是否为素数,但会有极小的概率误判。 在...

    最小生成树.pptx

    素数又称质数,一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。啊!1不是素数啊素数的判断啊,也耳熟能详了,暴力枚举一下除1和...

    哥德巴赫猜想的C语言精简实现

    这个猜想简单来说就是:任何大于2的偶数都可以表示为两个质数(素数)之和。虽然至今为止这个猜想尚未得到数学上的严格证明,但它在数论研究中占有重要的地位,并激发了无数数学家的研究热情。 在C语言中实现...

    大一萌新算法学习整理.pdf

    * 埃氏筛法:埃氏筛法是一种常见的筛法,通过在一系列数字中逐个标记出非质数来找到所有小于或等于某个数字的质数。 * 欧拉筛法:欧拉筛法是一种常见的筛法,通过使用欧拉函数来找到所有小于或等于某个数字的质数。 ...

    ACM常用代码

    筛法素数产生器 7.判断一个数是否素数 图论: 1.Prim 算法求最小生成 树 2.Dijkstra 算法求单源 最短路径 3.Bellman-ford 算法求 单源最短路径 4.Floyd 算法求每对节点 间最短路径 排序/查找: 1.快速排序 2.希尔...

    一、NOI数学之入门级(2021.09.27)B.pdf

    - **埃氏筛法和线性筛法**:两种求素数的高效算法,用于生成一定范围内的所有素数。 7. **快速幂取模**: - **快速幂取模算法**是一种高效计算大数次方模运算的方法,广泛应用于计算竞赛。它通过将指数二进制分解...

    noip算法总结noip算法总结.pdf

    - **筛法求素数**:埃拉托斯特尼筛法是一种高效找出所有小于给定数的素数的方法。 - **模运算规律公式**:了解模运算的基本性质,如模乘法、模加法、模幂运算等,对于解决模线性同余方程至关重要。 - **排列组合...

    ACM常用函数

    6. 筛法素数产生器:实现了筛法素数产生器的计算,使用了筛法算法。 7. 判断一个数是否素数:实现了判断一个数是否素数的计算,使用了筛法算法。 8. 求子距阵最大和:实现了子距阵最大和的计算,使用了动态规划算法...

    全国计算机等级考试三级网络技术上机考试分类题型(新思路).pdf

    【全国计算机等级考试三级网络技术】的上机考试主要涉及编程和算法的运用,特别是针对素数(质数)的处理。以下是对题型的详细分析: 1. **素数生成**:题目要求生成大于整数m且紧靠m的k个素数,通过循环检查并利用...

    程序设计竞赛ACM常用代码

    6. 筛法素数产生器:实现了筛法素数产生器的计算。 7. 判断一个数是否素数:实现了判断一个数是否素数的计算。 图论 1. Prim 算法求最小生成树:实现了 Prim 算法求最小生成树的计算。 2. Dijkstra 算法求单源最短...

    ACM常用代码.pdf

    6. 筛法素数产生器:实现筛法素数产生器的算法,可以用于生成素数。 7. 判断一个数是否素数:实现判断一个数是否素数的算法,可以用于判断一个数是否素数。 图论: 1. Prim 算法求最小生成树:实现Prim算法求最小...

    全国计算机等级考试三级网络技术上机考试分类题型新思路.pdf

    判断素数的常见方法有质数筛法、埃拉托斯特尼筛法或者简单的遍历除法验证。 2. **循环与条件判断**:题目的多数代码段都包含了循环结构(如`for`循环)和条件语句(如`if`),用于遍历数组元素并执行特定操作,如...

    ACM内部预定函数

    2. **筛法素数生成器**:使用埃拉托斯特尼筛法快速找出一定范围内的所有素数。 **图论**: 1. **最小生成树**:Prim算法和Kruskal算法用于找到无权图或加权图的最小生成树。 2. **最短路径**:Dijkstra算法、...

    NOI数学--2021.07.28(E).pdf

    - 埃氏筛法和线性筛法用于高效地求出一定范围内的所有素数。 4. 组合数学 - 加法原理和乘法原理是组合数学中解决问题的基本方法。 - 排列和组合的计算公式用于求解不同元素的有序和无序排列问题。 - 杨辉三角是...

    个人整理ACM模板.doc

    在ACM中,理解和应用素数筛法非常重要,因为许多问题涉及到素数和因子的计算。在文档中,`sieve`函数通过一个布尔数组`is_prime`标记每个数是否为素数,初始时假设所有数都是素数,然后从2开始,将所有2的倍数标记为...

Global site tag (gtag.js) - Google Analytics