质数判断
一 暴力
直接从2开始循环到n,如果n可以整除某个数,那么说明n不是质数。
#include <iostream>
using namespace std;
int main()
{int n;cin >>n;for(int i = 2;i<=n;i++){if(n % i == 0){cout << "不是质数";return 0;}}cout << "是质数";return 0;
}
二 暴力+优化
如果一个数不是质数,那么,在n ^1/2内必定会有他的因数出现,所以可以缩短循环的范围
#include <iostream>
#include <cmath>
using namespace std;
int main()
{int n;cin >>n;for(int i = 2;i<=sqrt(n);i++){if(n % i == 0){cout << "不是质数";return 0;}}cout << "是质数";return 0;
}
三 根据质数的分布规律
质数有一个分布规律——大于等于5的质数一定和6的倍数相邻(5和7,11和13)。但是和6的倍数相邻的数不一定是质数,二者不是充要条件。
由此进行剪枝,达到优化的效果。
#include<iostream>
#include<cmath>
using namespace std;
int prime(int num) //判断素数
{// 先把 1 2 3 解决if (num == 1)return 0;if (num == 2 || num == 3)return 1;// 不和6的倍数相邻 不是质数if (num % 6 != 1 && num % 6 != 5)return 0;// 最后只剩下和6相邻的,但是其中有非质数,需要判断int tmp = sqrt(num);// 此时步长可以增加为6,缩短查询时间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;
}
四 质数筛
更多推荐
质数
发布评论