赞
踩
参考博文:https://blog.csdn.net/Jonms/article/details/80464622
对于判断一个数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; }
运行结果:
2是素数
17是素数
18不是素数
若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; }
运行结果:
2是素数
307是素数
320不是素数
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。