C++如何判断一个数是不是素数
目录
- 如何判断一个数是不是素数
- 思路
- 实现代码
- 快速判断一个数是不是素数(质数)
- 朴素的方法
- 下面介绍一个更快的方法
如何判断一个数是不是素数
题目:判断一个数是不是素数,1 < N <= 50000
思路
判断n是否整除(求余是否等于0)大于1而小于sqrt(n)中的任何一个数,如果有则不是素数,否则是素数
实现代码
// 判断一个数是不是素数,1 < N <= 50000 #include <iostream> #include <cmath> using namespace std; // 如果为真,即是素数;否则,不是素数 bool isPrime(int n) { int i; for(i = 2; i <= sqrt(n); i++) { if((n % i) == 0) // 如果能被除了1和它本身的数整除,就不是素数 return false; } return true; // 是素数 } int main(int argc, const char * argv[]) { int n; bool isFlag; while(cin >> n) { isFlag = isPrime(n); // 调用判断是否是素数的函数 if(isFlag) cout << n << "是素数" << endl; else cout << n << "不是素数" << endl; } return 0; }
快速判断一个数是不是素数(质数)
朴素的方法
判断从2到sqrt(n)是否有数可以与其整除。
下面介绍一个更快的方法
质数有一个分布规律——大于等于5的质数一定和6的倍数相邻。栗子:5和7,11和13。
由此进行剪枝,达到优化的效果。
Code
#include<iostream> #include<cmath> using namespace std; int prime(int num) //判断素数 { if (num == 1) return 0; if (num == 2 || num == 3) return 1; if (num % 6 != 1 && num % 6 != 5) return 0; int tmp = sqrt(num); for (int i = 5; i <= tmp; i += 6) if (num % i == 0 || num % (i + 2) == 0) return 0; return 1; } int main() { int n; cin >> n; if (prime(n)) cout << "这个数是素数" << endl; else cout << "这个数不是素数" << endl; }
以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。
相关推荐
-
C/C++利用筛选法算素数的方法示例
什么是求素数 素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素数运行得非常快. i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数 称筛法 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法.据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274-194年)发明的,又称埃拉托斯特尼筛子. 具体做法是: 先把N个自然数按次序排列起来.1不是质数,也不是合
-
浅谈C++如何求等差素数列
题目 标题:等差素数列 2,3,5,7,11,13,....是素数序列. 类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列. 上边的数列公差为30,长度为6. 2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列. 这是数论领域一项惊人的成果! 有这一理论为基础,请你借助手中的计算机,满怀信心地搜索: 长度为10的等差素数列,其公差最小值是多少? 注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字. 题解 絮絮叨叨(骂骂咧咧 一开始
-
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++素数筛选法
素数(又称质数):指在大于一的自然数中,只能被1和它自身整除的自然数: 素数筛选法是指一种非常规的素数判定方法,比较高效率: 原理:任何数的整数倍必定不是素数,大于二的偶数必定不是素数. 我们以找出100以内的素数为例,利用原理,我们可以首先排除偶数是素数,然后进一步判断奇数 实现将偶数标记为0,素数标记为1:(也可以用一个bool数组将偶数标记为false,奇数标记为true) 下面是全部代码 #include <iostream> #include <cmath> #defin
-
C++回文数及素数问题计算方法
本文实例讲述了C++回文数及素数问题计算方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 编制一个返回值为bool型的函数isPrimer(),用于判断参数是否为素数,isPalindrome()用于判断参数是否是回文数,调用函数回答以下问题(可以分别编制几个程序完成,也可以在一个main()函数中完成,输出时,用明显的提示语,说明正在完成哪个任务.) (1)输出10000以内的所有素
-
判断一个数是不是素数的方法
给出一个数,判断这个数是不是素数: 复制代码 代码如下: #include <cmath> bool isPrime(int n) { int i; for (i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true;}
-
C++如何判断一个数是不是素数
目录 如何判断一个数是不是素数 思路 实现代码 快速判断一个数是不是素数(质数) 朴素的方法 下面介绍一个更快的方法 如何判断一个数是不是素数 题目:判断一个数是不是素数,1 < N <= 50000 思路 判断n是否整除(求余是否等于0)大于1而小于sqrt(n)中的任何一个数,如果有则不是素数,否则是素数 实现代码 // 判断一个数是不是素数,1 < N <= 50000 #include <iostream> #include <cmath> usin
-
解析利用javascript如何判断一个数为素数
判断是否为素数? 质数(prime number)又称素数,有无限个.质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数. 合数,数学用语,英文名为Composite number,指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数.与之相对的是质数(因数只有1和它本身,如2,3,5,7,11,13等等,也称素数),而1既不属于质数也不属于合数.最小的合数是4. <!DOCTYPE html> <html lang="en">
-
ruby判断一个数是否为质数(素数)示例
ruby判断一个数是否为质数 质数又称素数.一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数:(除0以外)否则称为合数 .根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积:而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的. 复制代码 代码如下: def prime?(num) res = [1] res << num if num == 0 || num == 1 return false end 2.upto(
-
C语言判断一个数是否为素数方法解析
一.概念介绍 素数又称为质数.一个大于1的自然数(从2开始),除了1和它本身外,不能被其他自然数整除的叫做素数,否则称为合数. 0和1既不是素数也不是合数,最小的素数是2. 二.代码 方法一: bool is_Prime(int num){ int i; for(i = 2;i <= sqrt(num);i++){ if(num % i == 0)//一旦发现有因子,则返回false return false; } return true; } 注意:在for循环判断时不能忘记 i <= sq
-
java如何判断一个数是否是素数(质数)
目录 java判断一个数是否是素数(质数) 质数(prime number)又称素数,有无限个 思路 java 求1-100之间的质数 质数定义: 1.质数实例一 2.质数实例二 3.质数实例三 4.质数实例四 5.质数实例五 6.质数实例六 java判断一个数是否是素数(质数) 质数(prime number)又称素数,有无限个 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数,这样的数称为质数. import java.util.Scanner; public class Te
-
C语言判断数是否为素数与素数输出
目录 1.判断单个数是否为素数(多组输入) 2.输入范围输出范围内的素数 3.总结 素数的概念:素数也叫质数,是一种只能被自己本身和1整除的数并且大于1,当然0与1不是素数. 1.判断单个数是否为素数(多组输入) 我的思路是,首先输入一个数,利用素数的概念来判断是非为素数,是的话输出素数:否则不输出. 关于素数的判断首先我们吧输入的数当初被除数,我选择用一个for循环来实现,从2开始当除数,每轮加1,一直循环去除被除数,一直除到被除数减一那个数,要是期间能被一个数整除则跳出循环不为素数,要是一直
-
JS判断一个数是否是水仙花数
水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身. 例如:1^3 + 5^3+ 3^3 = 153 //判断一个数是否数水仙花数 var num=prompt('请输入一个数字'); //得到位数可以计算幂数 var length=num.length; //使用字符串的方法获取每一位数 var content=num.split(""); //判断开始输入的数字和计算出来的结果是否相等 var result=0; for(var i=0;i&l
-
C语言判断一个数是否是2的幂次方或4的幂次方
快速判断一个数是否是2的幂次方,若是,并判断出来是多少次方! 将2的幂次方写成二进制形式后,很容易就会发现有一个特点:二进制中只有一个1,并且1后面跟了n个0: 因此问题可以转化为判断1后面是否跟了n个0就可以了. 如果将这个数减去1后会发现,仅有的那个1会变为0,而原来的那n个0会变为1:因此将原来的数与去减去1后的数字进行与运算后会发现为零. 最快速的方法: (number & number - 1) == 0 原因:因为2的N次方换算是二进制为10--0这样的形式(0除外).与上自己-1的
-
如何判断一个数是否为4的幂次方?若是,并判断出来是多少次方?
将4的幂次方写成二进制形式后,很容易就会发现有一个特点:二进制中只有一个1(1在奇数位置),并且1后面跟了偶数个0: 因此问题可以转化为判断1后面是否跟了偶数个0就可以了.4的整数次幂的二进制数都为 (4)100.(16)10000.(64)1000000......另外,4的幂次方4^n也可以写为2^(2*n),即也可以写为2的幂次方,当然就满足2的幂次方的条件了,即num & num-1==0.思路:首先用条件num & num-1==0来判断是否为2的幂次方,若不满足,则不是.若满足
随机推荐
- AngularJS应用开发思维之依赖注入3
- 基于使用paramiko执行远程linux主机命令(详解)
- 详解mysql中的冗余和重复索引
- Ruby中的Mechanize的使用教程
- 微信小程序 选择器(时间,日期,地区)实例详解
- js在数组中删除重复的元素自保留一个(两种实现思路)
- asp.net cookie的读写实例
- PHP中source #N问题的解决方法
- Python字符串处理实例详解
- 重写、隐藏基类(new, override)的方法
- Powershell小技巧之获取对象可变的特征
- 修改Linux主机名的方法
- JavaScript实现16进制颜色值转RGB的方法
- windows服务器安全设置之提权篇
- win2003 AspJpeg安装图文教程
- 详解CentOS 6.4 添加永久静态路由所有方法汇总
- Java中的final关键字详细介绍
- thinkphp实现163、QQ邮箱收发邮件的方法
- 轻松实现php文件上传功能
- Android UI效果之绘图篇(一)