质数算法

质数的一些定理

1. 质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
2. 每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。
3. 假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。
4. 假如n是合数，那么它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。即(n%6==1 || n%6 == 5) 为true.

质数判定方法

1. 穷举法 O(n^2) ，若穷举到sqrt(n)，则为O(n^1.5)
2. 穷举到sqrt(n)，但是在循环前先判定是否整除2，3，5，7且测试的数(被模的数)一次循环自增6，而不是1
3. 类似穷举，但是测试的数为所有<=sqrt(n)的质数。因为任何一个合数都分解质因数，写成几个质数相乘的形式，而这些质数作为约数，全部都<=sqrt(n)。若所有这样的测试数都不能被整除，说明这个数不是合数，也就是质数。这种方法用较小的质数表，具体的说，是<=sqrt(n)的所有质数组成的质数表，判断检测n的质数性。
4. 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