质数的判定及筛选_质数的筛选

我们都知道在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，也叫素数。

质数的判定：

我们一开始所选用的最原始的方法如下：

boolean is_prime(int n){
    if(n<2) return false;
    for(int i=2;i<n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

这里补充一个新的判定方法——试除法

一个数的约数都是成对出现的，比如a和（n/a）。所以我们枚举较小的那个数就好。

依照a和（n/a），可以得到：a<=（n/a）==> a^2<=n ==> a<=n^(1/2)

boolean is_prime(int n){
    if(n<2) return false;
    for(int i=2;i<=n/i;i++){
        if(n%i==0) return false;
    }
    return true;
}

 第n个质数

我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……

请你计算第 2019 个质数是多少？

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

利用质数的判定写出一个判断方法，利用该方法，返回true次数增加，直到次数==n得到所求值

public class Main {
	public static void main(String[] args) {
		int i=2;
		int cnt=1;
		while (cnt<2019) {
			i++;
			if (isPrime(i)) {
				cnt++;
			}
			
		}
		System.out.println(i);
		
	}
	static boolean isPrime(int i) {
		for (int j = 2; j <=i/j; j++) {
			if (i%j==0) {
				return false;
			}
		}
		return true;
	}
}

分解质因数

质因数就是一个数的约数，并且是质数。比如8=2×2×2，2就是8的质因数。12=2×2×3，2和3就是12的质因数。把一个式子以12=2×2×3的形式表示，叫做分解质因数。16=2×2×2×2,2就是16的质因数，把一个合数写成几个质数相乘的形式表示，这也是分解质因数。

要知道：一个数n中最多只包含一个大于n^(1/2)的质因子。

可以反证：假设有两个大于n^(1/2)的质因子，两者相乘就大于n，不成立。

void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            System.out.println(i+" "+s);
        }
    }
    if(n>1){//剩下这个数就是大于n^(1/2)的唯一一个质因子
        System.out.println(n+" "+1);
    }
}

质数的筛选方法

1、埃筛法（之前的笔记有写过这篇算是一个汇总吧）

2、线性筛

把每一个合数，用它的某一个质因子筛掉（n只会被最小质因子筛掉）

void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
        }
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;//primes[j]一定是i的最小质因子
        }
    }
}