当前位置:   article > 正文

判断素数(C++版)_c++判断素数

c++判断素数

参考博文:https://blog.csdn.net/Jonms/article/details/80464622

1.简单粗暴法

对于判断一个数n是否为素数,按素数的定义,试除以从2开始到m-1的整数,如果都不能整除,则该数一定是素数。

#include <iostream>
using namespace std;

bool IsPrime(int n)
{
	if(n <= 1){
		cout<<n<<"不是素数"<<endl; 
		return false;
	}
    for (int i = 2; i < n; i++)
    {
        if ((n % i) == 0){
            cout<<n<<"不是素数"<<endl;
            return false;
        }
    }
    cout<<n<<"是素数"<<endl;
    return true;
}

int main() {
    int a = 2, b = 17, c = 18;
    IsPrime(a);
    IsPrime(b);
    IsPrime(c);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

运行结果:

2是素数
17是素数
18不是素数
  • 1
  • 2
  • 3

2.更高效率的方法

若2都不能除尽,还要试4, 6, 8, …吗?若3都不能除尽,还要试9, 15, 21, …吗?等等。一个数,如果有因子的话,那么在它的平方根数以内就应该有,否则就没有因子。所以必定有一个因子不大于m的平方根。故判断m是否为素数,只要试除到m的平方根就可以了,不必一直到m-1。

#include <iostream>
#include <algorithm>
using namespace std;

bool IsPrime(int n)
{
	if(n <= 1){
		cout<<n<<"不是素数"<<endl; 
		return false;
	}
    for (int i = 2; i <sqrt(n); i++)
    {
        if ((n % i) == 0){
            cout<<n<<"不是素数"<<endl;
            return false;
        }
    }
    cout<<n<<"是素数"<<endl;
    return true;
}

int main() {
    int a = 2, b = 307, c = 320;
    IsPrime(a);
    IsPrime(b);
    IsPrime(c);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

运行结果:

2是素数
307是素数
320不是素数
  • 1
  • 2
  • 3
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/75304
推荐阅读
相关标签
  

闽ICP备14008679号