如何判断一个数是不是素数
题目：判断一个数是不是素数，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;
}以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
