C++两种素数判定方法

目录
  • 1.什么是素数
  • 2.素数的两种判断方法
    • （1）暴力法
      • 从 2 到 √n
      • 6n-1与6n+1
    • （2）筛法
      • 埃氏筛
      • 欧拉筛

1.什么是素数

素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是素数也不是合数）。

在许多的程序设计题目中，都会涉及到素数的判断，那我们该如何有效判断素数呢？

2.素数的两种判断方法

（1）暴力法

从 2 到 √n

根据素数的定义，我们可以使用逐个试除的方式来判断素数，如果能为要判断的数找到一个除了1和自身以外的因数，那么它就是合数；反之，就是素数。

而这样的因数的范围必然在 2 ~ √n之间，所以我们便可以得到以下代码。

int isPrime(int n)
{
	if(n <= 1)
	{
		return 0;
	}
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			return 0;
		}
	}
	return 1;
}

该函数就可以判断输入的数是否为素数。

这个范围还可以更进一步地缩小。

6n-1与6n+1

数学上有一个定理，除了2和3外，只有形如6n-1和6n+1的自然数可能是素数，这里的n是大于等于1的整数。

如何理解这个定理呢？

所有自然数都可以写成6n,6n+1,6n+2,6n+3,6n+4,6n+5这6种。 那么我们就可以得到下表。

自然数 是否可能是素数
6n 不可能，为2的倍数
6n+1 可能
6n+2 不可能，为2的倍数
6n+3 不可能，为3的倍数
6n+4 不可能，为2的倍数
6n+5 可能

其中6n+5可以写作6n-1，所以除了2和3的素数必然形如6n-1或6n+1。

于是我们可以写出如下代码。

int isPrime(int n)
{
	if(n <= 1) return 0;
	else if(n == 2 || n == 3) return 1;
	else if(n % 6 != 1 && n % 6 != 5) return 0;
	for (int i = 5; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			return 0;
		}
	}
	return 1;
}

优化后的算法具有更高的效率。

（2）筛法

暴力算法虽然可以判断某个数是否为素数，但是当它面对大量需要判断的数据时，它的效率会显得十分低下，我们也有更好地方法来求一定范围里的素数，它就是我们的筛法。

筛法，顾名思义，就是将合数从数据中筛除，剩下的自然就都是素数了。

筛法也分为两种，让我们来逐一介绍。

埃氏筛

埃拉托斯特尼 筛法，简称 埃氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

下面的程序就是通过埃氏筛判断 0 ~ MAXSIZE-1是否为素数。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = { 0 };
void sieveOfEratosthenes()
{
	for (int i = 2; i < MAXSIZE; i++)
	{
		isPrime[i] = 1;
	}
	for (int i = 2; i * i < MAXSIZE; i++)
	{
		if (isPrime[i])
		{
			for (int j = i * 2; j < MAXSIZE; j += i)
			{
				isPrime[j] = 0;
			}
		}
	}
}

埃氏筛的时间复杂度是O(n*loglogn)，效率相较于原来的暴力算法已经有了很大的提高，但它仍然有具有一定的不足。

对于多个素数的公倍数，可能会被多次筛去。

为了解决这个问题，数学家欧拉优化了算法，于是就有了新的筛法。

欧拉筛

欧拉筛法，简称欧拉筛或是欧式筛，又因为其O(n)的时间复杂度而被称为线性筛。

欧拉筛将合数分解为（最小质因数 * 一个合数）的形式，通过最小质因数来判断当前合数是否已经被标记过，与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。

下面的程序就是通过欧拉筛判断 0 ~ MAXSIZE-1是否为素数。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = { 0 };
int prime[MAXSIZE];
int cnt = 0;
void sieveOfEuler()
{
	for (int i = 2; i < MAXSIZE; i++)
	{
		prime[i] = 1;
	}
	for (int i = 2; i * i < MAXSIZE; i++)
	{
		if (isPrime[i])
		{
			prime[++cnt] = i;
		}
		for (int j = 1; i * prime[j] < MAXSIZE; j++)
		{
			isPrime[i * prime[j]] = 0;
			//若i为prime[j]的倍数，终止循环，避免重复筛除
			if (i % prime[j] == 0)
                break;
		}
	}
}

在求一定范围中的所有素数时，欧拉筛具有无可比拟的优势，在程序设计中也经常被采用。

到此这篇关于C++两种素数判定方法的文章就介绍到这了,更多相关C++素数判定内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++ 实现求小于n的最大素数的实例

    C++ 实现求小于n的最大素数的实例 枚举就是基于已有知识镜像答案猜测的一种问题求解策略 问题:求小于n的最大素数 分析: 找不到一个数学公式,使得根据N就可以计算出这个素数     我们思考: N-1是素数么?N-2是素数吗?...         所以我们就是判断N-K是否为素数:     N-K是素数的充分必要条件:N-K不能被[2,n-k)中任何一个整除         判断N-K是否为素数的问题可以转化为:     求小于N-K的全部素数(求"小于N的最大素数"中的条件是&q

  • 浅谈C++如何求等差素数列

    题目 标题:等差素数列 2,3,5,7,11,13,....是素数序列. 类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列. 上边的数列公差为30,长度为6. 2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列. 这是数论领域一项惊人的成果! 有这一理论为基础,请你借助手中的计算机,满怀信心地搜索: 长度为10的等差素数列,其公差最小值是多少? 注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字. 题解 絮絮叨叨(骂骂咧咧 一开始

  • C++回文数及素数问题计算方法

    C++回文数及素数问题计算方法

    本文实例讲述了C++回文数及素数问题计算方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 编制一个返回值为bool型的函数isPrimer(),用于判断参数是否为素数,isPalindrome()用于判断参数是否是回文数,调用函数回答以下问题(可以分别编制几个程序完成,也可以在一个main()函数中完成,输出时,用明显的提示语,说明正在完成哪个任务.) (1)输出10000以内的所有素

  • C/C++利用筛选法算素数的方法示例

    什么是求素数 素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素数运行得非常快. i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数 称筛法 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法.据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274-194年)发明的,又称埃拉托斯特尼筛子. 具体做法是: 先把N个自然数按次序排列起来.1不是质数,也不是合

  • c++素数筛选法

    c++素数筛选法

    素数(又称质数):指在大于一的自然数中,只能被1和它自身整除的自然数: 素数筛选法是指一种非常规的素数判定方法,比较高效率: 原理:任何数的整数倍必定不是素数,大于二的偶数必定不是素数. 我们以找出100以内的素数为例,利用原理,我们可以首先排除偶数是素数,然后进一步判断奇数 实现将偶数标记为0,素数标记为1:(也可以用一个bool数组将偶数标记为false,奇数标记为true) 下面是全部代码 #include <iostream> #include <cmath> #defin

  • C++如何判断一个数是不是素数

    目录 如何判断一个数是不是素数 思路 实现代码 快速判断一个数是不是素数(质数) 朴素的方法 下面介绍一个更快的方法 如何判断一个数是不是素数 题目:判断一个数是不是素数,1 < N <= 50000 思路 判断n是否整除(求余是否等于0)大于1而小于sqrt(n)中的任何一个数,如果有则不是素数,否则是素数 实现代码 // 判断一个数是不是素数,1 < N <= 50000 #include <iostream> #include <cmath> usin

  • C++两种素数判定方法

    目录 1.什么是素数 2.素数的两种判断方法 (1)暴力法 从 2 到 √n 6n-1与6n+1 (2)筛法 埃氏筛 欧拉筛 1.什么是素数 素数又称质数.一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做素数:否则称为合数(规定1既不是素数也不是合数). 在许多的程序设计题目中,都会涉及到素数的判断,那我们该如何有效判断素数呢? 2.素数的两种判断方法 (1)暴力法 从 2 到 √n 根据素数的定义,我们可以使用逐个试除的方式来判断素数,如果能为要判断的数找到一个除了1和自身以

  • 两种不同的方法实现js对checkbox进行全选和反选

    通过两种不同的方法实现用js来对checkbox进行全选和反选: 方法一: 1:js实现checkbox的 全选 功能: 复制代码 代码如下: function checkAll() { var code_Values = document.getElementsByTagName("input"); for(i = 0;i < code_Values.length;i++){ if(code_Values[i].type == "checkbox") { c

  • thinkPHP中钩子的两种配置调用方法详解

    thinkPHP中钩子的两种配置调用方法详解

    本文实例讲述了thinkPHP中钩子的两种配置调用方法.分享给大家供大家参考,具体如下: thinkphp的钩子行为类是一个比较难以理解的问题,网上有很多写thinkphp钩子类的文章,我也是根据网上的文章来设置thinkphp的钩子行为的,但根据这些网上的文章,我在设置的过程中,尝试了十几次都没有成功,不过,我还是没有放弃,最后还是在一边调节细节,一边试验的过程中实现了钩子行为的设置.下面是我个人的设置经验,在这里跟大家分享一下. 个人做了两种设置,都试验成功了,一个简单点,在thinkphp

  • JavaScript数值千分位格式化的两种简单实现方法

    在对数值进行格式化的时候,一个常见的问题是按照千分位格式化,网上对这个问题已经有很多种解决方法了,还可以利用Array.prototype.reduce方法来实现千分位格式化. function formatNumber(num) { if (isNaN(num)) { throw new TypeError("num is not a number"); } var groups = (/([\-\+]?)(\d*)(\.\d+)?/g).exec("" + nu

  • Java HashMap两种简便排序方法解析

    这篇文章主要介绍了Java HashMap两种简便排序方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 HashMap的储存是没有顺序的,而是按照key的HashCode实现. key=手机品牌,value=价格,这里以这个例子实现按名称排序和按价格排序. Map phone=new HashMap(); phone.put("Apple",8899); phone.put("SAMSUNG",7000);

  • c# 两种发送邮件的方法

    目录 一.两种发送邮件的方法 二.遇到的问题 三.示例 System.Web.Mail System.Net.Mail 一.两种发送邮件的方法 有用到两种方式发邮件,一种是用System.Web.Mail类,另一种是System.Net.Mail类. System.Net.Mail是作为System.Web.Mail的替代存在的. System.Web.Mail使用时会提示已过时,但目前任然可以正常使用. 二.遇到的问题 我在使用System.Net.Mail发邮件的时候遇到一个问题,如果是用的

  • Spring框架开发IOC两种创建工厂方法详解

    1.IOC有两种创建工厂的方法 IoC 通过工厂模式创建 bean 的方式有两种: 静态工厂方法 实例工厂方法 2.两种方法的不同 2.1静态方法创建 就是直接可以通过静态方法来实例化一个对象,采用类名.方法名的方式创建 public class HelloFactory { public static HelloWorld getInstance(){ return new Hello(); } } HelloWorldFactory.getInstance(); 2.2实例方法创建 采用ne

  • SpringBoot EasyPoi动态导入导出的两种方式实现方法详解

    SpringBoot EasyPoi动态导入导出的两种方式实现方法详解

    目录 前言 一.基于@Excel的 isColumnHidden 属性 1.1 实现原理 1.2 实现步骤 1.3 实现效果 二. 基于List< ExcelExportEntity > 的导出 实现效果 总结 前言 一开始为了图方便,使用的是土方法,即创建多个不同的实体类,每个实体类对应不同的列.这样虽说能实现,但实在不想多复制实体类,把代码堆的和shi山一样.于是查看官方文档,里面确实提供了更加优雅的实现方式.废话不多说,开整. 一.基于@Excel的 isColumnHidden 属性

  • 详解MySQL Shell 运行 SQL 的两种内置方法

    目录 第一.函数run_sql 如何使用: 第二.函数 sql 如何使用: 结论: MySQL Shell 是兼容 MySQL 传统命令行客户端的超级替代版,支持 SQL .JavaScript .Python 三种语言环境.工具自身包含了很多组件,使得 DBA 们管理 MySQL 更加便捷高效. 今天我们来介绍 MySQL Shell 的组件:MYSQLX 组件的两个检索函数在具体使用上的一些区别. MYSQLX 组件包含很多预置的类库, 其中与MySQL 交互最直接的就是 Session 类

  • 移动Web中图片自适应的两种JavaScript解决方法

    本文主要说的是Web中图片根据手机屏幕大小自适应居中显示,图片自适应两种常见情况解决方案.开始吧 在做配合手机客户端的Web wap页面时,发现文章对图片显示的需求有两种特别重要的情况,一是对于图集,这种文章只需要左右滑动浏览,最好的体验是让图片缩放显示在屏幕有效范围内,防止图片太大导致用户需要滑动手指移动图片来查看这种费力气的事情,用户体验大大降低.二是图文混排的文章,图片最大宽度不超过屏幕宽度,高度可以auto.这两种情况在项目中很常见.另外,有人说做个图片切割工具,把图片尺寸比例都设定为统

随机推荐