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;
}

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

赞 (0)

相关推荐

  • 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++素数筛选法

    c++素数筛选法

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

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

    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语言判断数是否为素数与素数输出

    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的幂次方,若不满足,则不是.若满足

随机推荐