C语言求质数的几种简单易懂方式

目录
  • 一. 暴力枚举
  • 二. 暴力求解的优化版本
  • 三.埃拉托斯特尼筛法
    • 细节部分
      • 1. 怎样选一批素数能将区间内所有合数都筛完？
      • 2.筛选过程具体是怎样的？
      • 3.具体代码
  • 总结

质数就是除了1和它本身外没有其他因数

一. 暴力枚举

假设现在有一个数num，要求我们判断是否是质数，由定义知我们可以遍历从2到 num-1的所有数，假

设都不能被整除，则num是质数，否则不是，C语言代码实现如下。

其中track用来检测是否遍历完从2到num-1的所有数

int main()
{
	int n = 0;
	int track = 0;
	printf("请输入要判断的数: ");
	scanf("%d", &n);
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0)
		{
			track = 1;
			break;
		}
	}
	if (track == 1)
		printf("这个数不是质数\n");
	else
		printf("这个数是质数\n");
	return 0;
}

二. 暴力求解的优化版本

实际上我们只需要遍历从2到√num的数就可以了。

因为对于非质数num来说有 a * b = num；其中a和b不可能同时大于√num，也就是说num是非质数的充要条件是在 [2,num-1]的区间上有因数,根据这一点可以对代码进行优化。

int main()
{
	int n = 0;
	int track = 0;
	printf("请输入要判断的数: ");
	scanf("%d", &n);
		for (int i = 2; i <= sqrt(n); i++)
		{
			if (n % i == 0)
			{
				track = 1;
				break;
			}
		}
		if (track == 1)
			printf("这个数不是质数\n");
		else
			printf("这个数是质数\n");

	return 0;
}

三.埃拉托斯特尼筛法

如果要求我们判断的数字很多，那么上面两种方法的效率就极其低下，因为每判断一个数都要从2开始遍历，计算机会做很多重复操作。

换一种思路，我们可以选一批质数，质数的倍数是合数（非质数），那么就可以把这些合数筛掉，经过多轮筛选后剩下的就全部是质数了。

看了前面的叙述可能有的朋友会有点懵，我解释一下。

细节部分

1. 怎样选一批素数能将区间内所有合数都筛完？

从2开始到√n的所有素数。首先1肯定没有筛选功能（1的任意倍数都是其本身）。

对于√n之后的素数，比如说用√n + 1进行筛选 ，得到的可筛选的数是 [(√n + 1) *  2, (√n +1) * √n] 中的整数，但是这些整数都有一个小于等于√n的约数，因此在我们遍历前面的数时已经将他们删除掉了，所以没必要重复，只需要 [2,√n)的所有素数即可。

2.筛选过程具体是怎样的？

不清楚筛选过程的朋友可以看看这张图，这张图搬运 自公众号 “coder梁”，做的特别清楚。

3.具体代码

C语言实现。

int main()
{
	//埃式筛法
	int n = 0;
	printf("请输入要判断的数 ");
	scanf("%d", &n);
	int* prime = (int*)malloc(n * sizeof(int));//定义一个可以存放n个数的数组
	if (!prime)
	{
		printf("创建数组失败\n");
		exit(-1);
	}
	//将prime数组全部初始化成1，表示全部是素数
	for (int i = 0; i < n; i++)
	{
		prime[i] = 1;
	}
	//从2开始筛选
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (prime[i - 1])        //如果是质数
		{
			for (int j = i * i; j <= n; j += i) //则将其剔除
				prime[j - 1] = 0;
		}
	}
	//打印
	for (int i = 0; i < n; i++)
	{
		if (prime[i] != 0)
			printf("%d ", i + 1);
	}
	printf("\n");
	return 0;
}

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C语言如何使用函数求素数和举例

    本题要求实现一个判断素数的简单函数.以及利用该函数计算给定区间内素数和的函数.素数就是只能被1和自身整除的正整数. 注意:1不是素数,2是素数. 函数接口定义: int prime( int p ); int PrimeSum( int m, int n ); 其中函数prime当用户传入参数p为素数时返回1,否则返回0:函数PrimeSum返回区间[m, n]内所有素数的和.题目保证用户传入的参数m≤n. 裁判测试程序样例: #include <stdio.h> #include <m

  • c语言求出给定范围内的所有质数

    程序功能: 输入一个整数,要求打印出这个整数以内的所有质数. 程序示例: #include <stdio.h> #include <stdlib.h> #include <math.h> bool IsPrime(int x) { bool bResult = false; int i, k; k = (int)sqrt(x); for (i = 2; i <= k; i++) { if (x % i == 0) { break; } } if (i > k

  • C语言用递归函数对素数进行判断流程

    目录 前言 思路简述 代码实现 前言 本文介绍递归函数实现素数判断. 事实上,递归算法判断素数的本质是试除法,且递归算法在本题中并不具有优势.它不仅没有优化原算法,还增加了空间复杂度与时间复杂度. 时间复杂度和空间复杂度都是0(N),实现效率可想而知. 那为什么还要写呢?仅作为开拓思路.加深对递归函数的理解而为之.其实很多基础的算法,包括斐波那契数列.闰年等,都可以用递归实现.递归思路能将复杂的问题呈现以简单的思路,这是它的优势.通过简单问题的递归实现,大家可以提前熟悉递归的构造和运用,为后续学

  • C语言求素数的几种方式总结

    目录 一.判断n是否能被2~n-1整除 方法一 方法二 二.判断n是否能被2~√n间的整数整除 方法一 方法二 总结 一.判断n是否能被2~n-1整除 输入的数n不能被2-(n-1)整除,说明是素数 输入的数n能被2-(n-1)整除,说明不是素数 注意:1不是素数,素数是指大于1的自然数,除了1和该数自身外,无法被其他自然数整除的数. 方法一 #include<stdio.h> int main() { int i, n; printf("请输入一个数:"); scanf(

  • C语言算法练习之数组求素数

    C语言算法练习之数组求素数

    目录 一.问题描述 二.算法实例编译环境 三.算法实例实现过程 3.1.包含头文件 3.2.声明数组 3.3.声明相关变量 3.4.数组赋值 3.5. 输出数组里面元素的值 3.6.求素数.素数和.最大的素数 3.7.输出所求的素数.素数和.最大的素数 四.经典算法实例程序 4.1.main.h文件 4.2.main.c文件 五.总结 一.问题描述 数组求素数 问题的描述 如下几点所示 输出1750 到 1850 之间的素数. 计算并输出1750 到 1850 之间的素数之和 S. 并且输出最大

  • C语言中判断素数(求素数)的思路与方法实例

    目录 前言 思路1实现: 思路2实现: <C与指针>4.14-2: 补充:判断素数的4种方法实例 总结 前言 素数又称质数.所谓素数是指除了 1 和它本身以外,不能被任何整数整除的数,例如17就是素数,因为它不能被 2~16 的任一整数整除. 思路1):因此判断一个整数m是否是素数,只需把 m 被 2 ~ m-1 之间的每一个整数去除,如果都不能被整除,那么 m 就是一个素数. 思路2):判断方法还可以简化.m 不必被 2 ~ m-1 之间的每一个整数去除,只需被 2 ~  之间的每一个整数去

  • C语言求质数的几种简单易懂方式

    目录 一. 暴力枚举 二. 暴力求解的优化版本 三.埃拉托斯特尼筛法 细节部分 1. 怎样选一批素数能将区间内所有合数都筛完? 2.筛选过程具体是怎样的? 3.具体代码 总结 质数就是除了1和它本身外没有其他因数 一. 暴力枚举 假设现在有一个数num,要求我们判断是否是质数,由定义知我们可以遍历从2到 num-1的所有数,假 设都不能被整除,则num是质数,否则不是,C语言代码实现如下. 其中track用来检测是否遍历完从2到num-1的所有数 int main() { int n = 0;

  • Java求质数的几种常用算法分析

    本文实例讲述了Java求质数的几种常用算法.分享给大家供大家参考,具体如下: 1.根据质数的定义求 质数定义:只能被1或者自身整除的自然数(不包括1),称为质数. 利用它的定义可以循环判断该数除以比它小的每个自然数(大于1),如果有能被它整除的,则它就不是质数. 对应代码是: void printPrime(int n){//判断n是否是质数 boolean isPrime=true;//是否是质数的标志 for(int i=n-1;i>1;i-){//n除以每个比n小比1大的自然数 if(n%

  • python求质数的3种方法

    本文为大家分享了多种方法求质数python实现代码,供大家参考,具体内容如下 题目要求是求所有小于n的质数的个数. 求质数方法1: 穷举法: 根据定义循环判断该数除以比他小的每个自然数(大于1),如果有能被他整除的就不是质数: def countPrimes1(self, n): """ :type n: int :rtype: int """ if n<=2: return 0 else: res=[] for i in range(2,

  • 详解java倒计时三种简单实现方式

    详解java倒计时三种简单实现方式

    写完js倒计时,突然想用java实现倒计时,写了三种实现方式 一:设置时长的倒计时: 二:设置时间戳的倒计时: 三:使用java.util.Timer类实现的时间戳倒计时 代码如下: package timer; import java.util.Calendar; import java.util.Date; import java.util.Timer; import java.util.TimerTask; /** * java演示倒计时 * */ public class TimeTes

  • C语言求阶乘之和的三种实现方法(先阶乘再累加)

    C语言求阶乘之和的三种实现方法(先阶乘再累加)

    目录 题目: 方法一:使用一层for循环实现 代码简单快捷容易理解 方法二:使用两层for循环嵌套 方法三:函数递归实现 总结 题目: 此处题目是以1-20的阶乘之和举例 方法一:使用一层for循环实现 代码简单快捷容易理解 代码示例如下: #include<stdio.h> int main() { double a = 1, sum = 0;//因为最后值可能会超出int所能接收的范围 故用double int n, i; scanf("%d", &n);//注

  • 用C语言模仿Python函数的一种简单实现方法

    首先得说明一点,C 语言不是函数式编程语言,要想进行完全的函数式编程,还得先写个虚拟机,然后再写个解释器才行(相当于 CPython ). 下面我们提供一个例子,说明 C 语言函数可以"适度地模仿" Python 函数. 我们有如下的 Python 程序: def line_conf(a, b): def line(x): return a*x + b return line line1 = line_conf(1, 1) line2 = line_conf(4, 5) print(l

  • C语言求圆周率的简单实现方法

    本文实例讲述了C语言求圆周率的方法.分享给大家供大家参考,具体如下: #include <stdio.h> #include <math.h> void main() { int s; float n,t,pi; t=1,pi=0;n=1.0;s=1; while(fabs(t)>1e-6) { pi=pi+t; n=n+2; s=-s; t=s/n; } pi=pi*4; printf("pi=%10.6f/n",pi); } 此处得出的结果可精确到小数

  • C语言求两个正整数的最大公约数示例代码

    目录 前言 1.穷举法 2.欧几里得算法(辗转相除法) 3.递归方法 附:相减法 总结 前言 两个正整数的最大公约数(Greatest Common Divisor, GCD)是能够整除这两个整数的最大整数.两个正整数的最大公约数的求法有多种解答,本文就三种方法做详细介绍:穷举法.欧几里得算法(辗转相除法).递归方法. 我们从一道问题来引入:编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的最大公约数. 1.穷举法 根据最大公约数的定义,我们可以采用一种最简单的方

  • 调整优化您的LAMP应用程序的5种简单方法

    调整优化您的LAMP应用程序的5种简单方法

    简介 Wikipedia.Facebook 和 Yahoo! 等主要 web 属性使用 LAMP 架构来为每天数百万的请求提供服务,而 Wordpress.Joomla.Drupal 和 SugarCRM 等 web 应用程序软件使用其架构来让组织轻松部署基于 web 的应用程序. 该架构的优势在于其简单性.而 .NET 这样的堆栈和 Java™ 技术可能使用大量硬件.昂贵的软件栈和复杂的性能调优,LAMP 堆栈可以运行于商品硬件之上,使用开源软件栈.由于软件栈是一个松散的组件集,而非一个整体堆

随机推荐