C语言实现求解素数的N种方法总结

目录
  • 前言
  • 必备小知识
  • C语言详解《试除法》求解素数
    • 试除法境界1
    • 试除法境界2
    • 试除法境界3
    • 试除法境界4
  • C语言详解《筛选法》求解素数
    • 筛选法境界5

前言

哈喽各位友友们,我今天又学到了很多有趣的知识,现在迫不及待的想和大家分享一下!我仅已此文,手把手带领大家探讨利用试除法、筛选法求解素数的n层境界!都是精华内容,可不要错过哟!!!

必备小知识

质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定1既不是质数也不是合数)。这里以求解100~200之间的素数举例讲解

C语言详解《试除法》求解素数

试除法境界1

境界1实现思路分析:

  • 首先,利用第一层for循环产生100~200的整数;
  • 其次,利用第二层for循环产生2~ i - 1之间的整数,并让100到200之间的每一个数和2到 i - 1之间的整数试除。
  • 定义flag变量,若flag为0,则不是素数;若flag为1,则是素数。
  • 定义count变量,记录试除次数。
  • 境界1算法的理性分析:境界1,简单来说就是让每一个数i和2~ i-1的数试除,这是最简单的想法,但是算法的效率是最低的~

看了文字的描述,大家可能理解的还是不够深刻。这里俺亲自敲出代码辅助大家理解~

境界1源码:

#include<stdio.h>
int main()
{

    int count = 0;//记录试除次数
    int i = 0;
    int j = 0;
    for (i = 100; i <= 200; i++)
    {
        int flag = 1;//flag最终结果为1,表示i是素数,为0表示不是素数。
        for (j = 2; j < i; j++)
        {
            count++;
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        }
        if(flag == 1)
        printf("%d ", i);
    }
    printf("\n境界1试除总次数:%d", count);
    return 0;
}

代码结果运行图:

由境界1求解100~200之间的素数,需要试除3292次!!!可见其算法效率如何啦。

试除法境界2

境界2实现思路分析:

  • 首先利用第一层for循环产生101~199的整数,这是和境界1最本质的区别!为什么这样设计呢?原因很简单,因为100到200之间的偶数一定不是素数,可以不用参与试除过程。
  • 其次,利用第二层for循环产生2~ i - 1之间的整数,并让101到199之间的每一个数和2到 i -1之间的整数试除。
  • 定义flag变量,若flag为0,则不是素数;若flag为1,则是素数。
  • 定义count变量,记录试除次数。
  • 境界2算法的理性分析:境界2和境界1类似,就是让每一个数i和2~ i-1的数试除,但是境界2能够提前让一些本不可能是素数的整数(100—200间的偶数)提前排除掉~

境界2源码:

#include<stdio.h>
int main()
{

    int count = 0;//记录试除次数
    int i = 0;
    int j = 0;
    for (i = 101; i < 200; i+=2)//提前排除100到200之间的偶数,符合这个条件一定不是素数。
    {
        int flag = 1;//flag最终结果为1,表示i是素数,为0表示不是素数。
        for (j = 2; j < i; j++)
        {
            count++;
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        }
        if(flag == 1)
        printf("%d ", i);
    }
    printf("\n境界2试除总次数:%d", count);
    return 0;
}

代码结果运行图:

由境界2求解100~200之间的素数,需要试除3241次,稍微比境界1好那么一丢丢啦!但是其算法效率还是不尽人意。

试除法境界3

境界3实现思路分析:

  • 首先,利用第一层for循环产生100~200的整数;
  • 其次,利用第二层for循环产生2~ sqrt(i)之间的整数,并让101到199之间的每一个数和2到 sqrt(i)之间的整数试除。为什么这样设计呢?设计思路分析:因为任何一个不是素数的数即合数,都一定可以进行因式分解。这里已16举例说明,16 = 2 * 8 = 4 * 4 。因此如果16被2整除就可以判定16不是素数了,就不用那2到 i - 1的每一个数都试除一遍啦。 因此,只需要拿2 ~sqrt(i)的数试除即可,这样大大提高了算法的效率!
  • 定义flag变量,若flag为0,则不是素数;若flag为1,则是素数。
  • 定义count变量,记录试除次数。
  • 境界3算法的理性分析:境界3相比于前面两种境界,做了很大的改进!让每一个数试除的测试减少了至少一半,大大减少了试除的次数,从而大大提高了算法的效率!!!

境界3源码:

#include<stdio.h>
#include<math.h>
int main()
{

	int count = 0;//记录试除次数
	int i = 0;
	int j = 0;
	for (i = 100; i <= 200; i++)
	{
		int flag = 1;//flag最终结果为1,表示i是素数,为0表示不是素数。
		for (j = 2; j <= sqrt(i); j++)//只需要试除2到sqrt(i)之间的整数即可
		{
			count++;
			if (i % j == 0)
			{
				flag = 0;
				break;
			}

		}
		if (flag == 1)
			printf("%d ", i);
	}
	printf("\n境界3试除总次数:%d", count);
	return 0;
}

代码结果运行图:

由境界4求解100~200之间的素数,只需要试除393次,相比于境界1和境界2的算法效率来说,已经有长足的改进啦!

试除法境界4

境界4实现思路分析:

  • 首先,采用境界2的算法思想。利用第一层for循环产生101~199的整数。
  • == 其次,利用境界三的试除想法,拿2 ~sqrt(i)的数试除。==
  • 定义flag变量,若flag为0,则不是素数;若flag为1,则是素数。
  • 定义count变量,记录试除次数。
  • 境界4算法的理性分析:境界4相比于境界3,再做优化!先排除掉偶数。

境界4源码:

#include<stdio.h>
#include<math.h>
int main()
{

	int count = 0;//记录试除次数
	int i = 0;
	int j = 0;
	for (i = 101; i < 200; i += 2)//排除100到200之间的2的倍数,符合这个条件一定不是素数。
	{
		int flag = 1;//flag最终结果为1,表示i是素数,为0表示不是素数。
		for (j = 2; j <= sqrt(i); j++)//只需要试除2到sqrt(i)之间的整数即可
		{
			count++;
			if (i % j == 0)
			{
				flag = 0;
				break;
			}

		}
		if (flag == 1)
			printf("%d ", i);
	}
	printf("\n境界4试除总次数:%d", count);
	return 0;
}

代码结果运行图:

由境界4求解100~200之间的素数,试除总次数为342,是,综合考虑了境界2和境界3的改良思想,已经达到了试除法的最高境界啦!

C语言详解《筛选法》求解素数

预备小知识

埃拉托色尼是一名古希腊的地理学家,他是世界上第一个计算出地球周长的人。埃拉托色尼素数筛选法可以很快速的计算出1到N之间的所有素数。埃拉托色尼素数筛选法大概的计算思路是:将n开根号,即N^0.5 ,去掉2到N^0.5中所有素数的倍数,剩下的数便都是素数了。例如求1到25中的素数有哪些,第一步是将25开根号,得到5;第二步将2到5的素数取出来,分别是2、3、5:再将2到25中且是2、3、5的倍数的数去掉,即去掉4、6、8、9、10、12、14、15、16、18、 20、21、22、24、25;剩下2、3、5、7、11、13、17、19便是1到25中的所有素数了。从上面我们可以看出筛选法和试除法其实有着本质上的区别,试除法是判断每一个数是不是素数来达到目的;而筛选法不是如此,筛选法是将不是素数的数全部去除,然后得到余下的数来达到目的~

境界5(基础筛选法)实现思路分析:

  • 首先,找到最小的质数2,再把范围内的所有2的倍数去掉;然后接下来找次小的质数3,再把所有3的倍数去掉;接着往复筛选去除,剩下的那些就全是素数啦!
  • 这里需要设计一个数组,只要满足上述这些步骤,即将大于1的且是2、3、4…的倍数全部置为0。最终不是0的数就是所谓的素数啦!

筛选法境界5

境界5源码:

#include<stdio.h>
int main()
{
    int i = 0;
    int j = 0;
    int arr[100];
    int count = 0;
    for (i = 0; i < 100; i++)
    {
        arr[i] = 100 + i;//将数组先初始化存储100到199。
                        //没有存储200也没关系,200一定不是素数

    }
    for (i = 0; i < 100; i++)
    {
        j = i + 1;
        while (j > 1)
        {
            count++;
            if (arr[i] % j == 0)
                arr[i] = 0;
            j = j - 1;
        }
    }
    for (j = 1; j < 100; j++)
    {
        if (arr[j] != 0)
        {
            printf("%d ", arr[j]);
        }
    }
    return 0;
}

代码结果运行图:

到此这篇关于C语言实现求解素数的N种方法总结的文章就介绍到这了,更多相关C语言求解素数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 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语言中判断素数(求素数)的思路与方法实例

    目录 前言 思路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和自身整除的正整数. 注意: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语言算法练习之数组求素数

    目录 一.问题描述 二.算法实例编译环境 三.算法实例实现过程 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语言实现的统计素数并求和代码分享

    题目来源于PAT平台,此题又是费了一番脑子.题目要求输出给定区间内的素数个数并对他们求和.具体思路是利用循环判断素数,将结果传递给控制变量,由控制变量再来判断是否执行自增以及求和.当然这里必须要注意1既不是素数也不是合数. 下面是代码: 复制代码 代码如下: #include <stdio.h> int main () {  int a=0,b=0;  int n=0,sum=0;  int x=0,i=0;  scanf("%d %d",&a,&b);  

  • C语言实现求梅森素数的代码与解析

    问题描述 梅森数(Mersenne Prime)指的是形如2n-1的正整数,其中指数n是素数,即为Mn.如果一个梅森数是素数,则称其为梅森素数.例如22-1=3.23-1=7都是梅森素数. 当n=2,3,5,7时,Mn 都是素数,但n=11时,Mn=M11=211-1=2047=23X89,显然不是梅森素数. 1722年,瑞士数学大师欧拉证明了231-1=2147483647是一个素数,它共有10位数,成为当时世界上已知的最大素数. 迄今为止,人类仅发现了47个梅森素数.梅森素数历来都是数论研究

  • 使用c语言判断100以内素数的示例(c语言求素数)

    从console输入一个数,判断这个数是否为素数(质数). 复制代码 代码如下: #include <stdio.h> /**判断100以内的素数*/ //定义函数判断是否是素数int isPrime(int num ){    int i;    //从2开始循环,一直到i的平方小于等于给定的数.    for (i = 2; i*i <= num; i++) {        if ( ( num % i ) == 0 ) {            return 0;       

  • python判断所输入的任意一个正整数是否为素数的两种方法

    素数(也称质数),是指除了1和该数本身,不能被任何正整数整除的正整数.判断一个正整数m是否为素数,只要判断m可否被2~根号m之中的任何一个正整数整除,如果m不能被此范围中任何一个正整数整除,m即为素数,否则m为合数. 方法一:(利用for循环和break语句) import math m = int(input("请输入一个整数(>1):")) k = int(math.sqrt(m)) for i in range(2, k+2): if m % i == 0: break #

  • C语言实现倒置字符串的两种方法分享

    目录 前言 一.题目 二.思路讲解 三.代码实现 四.代码总结 五.第二种方法倒置字符串 六.总结 前言 今天在牛客网上刷了一道题,我感觉挺有意义的,现在我就分享给大家,并且告诉大家解题思路. 一.题目 事例: 输入下列字符: I like beijing. 输出的字符: beijing. like I 二.思路讲解 1.设立一个数组存放输入的字符串 2.将其中每个单词进行逆置 得到 I ekil .gnjieb 3.再将字符串逆置  得到beijing.like I 三.代码实现 1.设立一个

  • R语言将变量分组的3种方法实例(含cut函数说明)

    目录 前言 方法一:直接对分组变量进行赋值 方法二:使用within函数对变量进行分组 方法三:采用cut函数 总结 前言 在数据处理的过程中,我们有时候需要将连续的数值数据转换为类别数据,比如将收入分成高.中和低三组,将学生成绩分为优.良.中.及格和不及格五组. 本来将基于R语言,采用三种方法来实现:第一种是对变量直接进行重新赋值,第二种是使用within函数对语句进行组织,第三种是cut函数. 首先我们定义一个数据框,这个数据框包括学生姓名和数学成绩两个变量. #定义数据框 mathScor

  • C语言格式输出二进制的2种方法总结

    目录 1.前言 2.源码实现 3.结果展示 附:C语言如何将一个数字的二进制形式输出出来 总结 1.前言 在我们日常的编程中,有时候需要格式化输出一个整形数据的二进制,但是在我们C语言中只有 输出十进制:%d: 输出十六进制:%x: 输出单个字符:%c: 输出字符串:%s: 输出变量所在的地址:%p: 而并没有这种二进制对应的格式,所以需要我们手动来实现. 2.源码实现 本篇博客给大家介绍两种方法: 1.通过库函数itoa,需要包含头文件:#include <stdlib.h>: 2.通过十进

  • R语言导入导出数据的几种方法汇总

    导出: 对于某一数据集导出文件的方法 导出例子:write.csv(data_1,file = "d:/1111111111.csv") 其中data_1是你的数据集,file是你的存储路径和要存储的名字 导入: 1  使用键盘输入数据 (1) 创建一个空数据框(或矩阵),其中变量名和变量的模式需与理想中的最终数据集一致: (2)针对这个数据对象调用文本编辑器,输入你的数据,并将结果保存回此数据对象中. 在下例中,你将创建一个名为mydata的数据框,它含有三个变量:age(数值型).

  • Go读取文件与写入文件的三种方法操作指南

    目录 文件写入操作 Write和WriteString写入操作 使用buffio内置包来读文件 第三种写入文件方法:ioutil.WriteFile 总结 打开和关闭文件操作: os.Open()函数能够打开一个文件,返回一个*File和一个err.对得到的文件实例调用close()方法能够关闭文件. package main import ( "fmt" "os" ) //文件操作 func main(){ //打开文件 file, err := os.Open(

  • C语言二分法求解方程根的两种方法

    本文实例为大家分享了C语言二分法求解方程根的具体代码,供大家参考,具体内容如下 对于二分法求根,其实和弦截法思想很像,甚至更简单. 原理:先看如下的图 A,B两个点为跟的一个边界,通过一直缩小跟的边界,从而获取跟的值. (1)知道函数(即方程的式子),这个好说,题上都有 (2)循环的输入A,B的横坐标的值,即x1,x2的初值,直到f(x1)与f(x2)的乘积为负数才停止.(必须保证方程的跟在(x1,x2)区间)这样的x1,x2的初值才有意义. (3)令xx=(x1+x2)/2;(即中值),若f(

  • C语言实现求解最小公倍数的算法示例

    目录 题目描述 问题分析 方法一:穷举法 方法二:定理法 题目描述 求任意两个正整数的最小公倍数 问题分析 两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数.整数a,b的最小公倍数记为[a,b],同样的,a,b,c的最小公倍数记为[a,b,c],多个整数的最小公倍数也有同样的记号. .与最小公倍数相对应的概念是最大公约数,a,b的最大公约数记为(a,b).关于最小公倍数与最大公约数,我们有这样的定理:(a,b)x[a,b]=ab(a,b均为整数)

  • 详解C语言快速排序三种方法的单趟实现

    目录 交换排序的思想 冒泡排序的思想 快速排序的整体框架 快速排序单趟实现逻辑 1. hoare版本单趟实现(左右指针法) 2.挖坑法单趟排序实现 3.前后指针法 交换排序的思想 基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排 序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动. 冒泡排序的思想 冒泡排序比较简单,我们之前使用也很多,简单讲解,就是比较两个数,如果比他大就交换,没有他大就接着向后比,一直到数组结束,这是单趟

随机推荐

其他