质数的一些定理
- 质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
- 每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。
- 假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。
- 假如n是合数，那么它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。即(n%6==1 || n%6 == 5) 为true.
质数判定方法
- 穷举法 O(n^2) ，若穷举到sqrt(n)，则为O(n^1.5)
- 穷举到sqrt(n)，但是在循环前先判定是否整除2，3，5，7且测试的数(被模的数)一次循环自增6，而不是1
- 类似穷举，但是测试的数为所有<=sqrt(n)的质数。因为任何一个合数都分解质因数，写成几个质数相乘的形式，而这些质数作为约数，全部都<=sqrt(n)。若所有这样的测试数都不能被整除，说明这个数不是合数，也就是质数。这种方法用较小的质数表，具体的说，是<=sqrt(n)的所有质数组成的质数表，判断检测n的质数性。
- Miller-Rabin+二次判定
方法2的代码
public static boolean isPrime(int num) {
if (num <= 3) {
return num > 1;
}
if(num == 5) return true;
if(num == 7) return true;
if(num%2==0 || num%3==0 || num%5==0 || num%7==0)
return false;
// 不在6的倍数两侧的一定不是质数
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 6) { // 步进为6
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
方法3的代码
bool isPrimeNumber(int n, int PNarray[]){
for(int i = 0; PNarray[i] * PNarray[i] <= n; i++){
if(n % PNarray[i] == 0){
return false;
}
}
return true;
}
PAT-B1003 数素数，采用方法3
#include <stdio.h>
#include <iostream>
using namespace std;
int PNarray[10000] = {2}; //PNarray[0] = 2;
bool isPrimeNumber(int n, int PNarray[]){
for(int i = 0; PNarray[i] * PNarray[i] <= n; i++){
if(n % PNarray[i] == 0){
return false;
}
}
return true;
}
int main(){
int a, b;
scanf("%d %d", &a, &b);
int index = 1;
for(int i = 3; index < b; i += 2){ //建立到第b个数的素数表
if(isPrimeNumber(i, PNarray)){ //is prime number
PNarray[index++] = i; //store in prime number table
}
}
int count = 0;
for(int j = a - 1; j < b; j++){
if(count % 10 != 0){
printf("%c", ' ');
}
printf("%d", PNarray[j]);
count++;
if(count % 10 == 0){
printf("%c", '\n');
}
}
if(count % 10 != 0){
printf("%c", '\n');
}
return 0;
}
参考
https://blog.csdn.net/afei__/article/details/80638460
https://www.zhihu.com/question/19668324
