质数: 只有1和本身两个约数的数

（埃氏筛法就不写了，直接上欧拉筛 ，yyds！！）

方法一：暴力大法

​ 每一个整数都可以看做由两个数相乘得到，且每个乘数不大于原整数的平方根（可以减少相应的时间复杂度），本质还是暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Scanner;

public class PrimeCheck {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println(isPrime(n)?"yes":"no");
		}
	}
	
	public static boolean isPrime(int n) {
		if(n<=1) return true;
		for(int i=2;i<=n/i;i++) if(n%i==0) return false;
		return true;
	}
}

方法二：欧拉筛（线性筛）

核心思路 ：每个合数只被其最小的素因子筛一次，大大减少了时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] prim = new int[n];
		boolean[] isp = new boolean[n];
//		质数为false，合数为true
		int count = 0;
//		i是boolean数组的指针
//		j是prim数组的指针
		for (int i = 2; i < isp.length; i++) {
			if (isp[i] == false)
				prim[count++] = i;
			for (int j = 0; j < count && i * prim[j] < n; j++) {
//				保证素数的倍数不超过打表区间
				isp[i * prim[j]] = true;
//				质数的倍数一定是合数
				if (i % prim[j] == 0)
					break;
//				欧拉筛的核心  每个合数只被其最小的素因子筛一次
			}
		}
		System.out.println(count);
		for (int i = 0; i < n; i++) {

			if (prim[i] != 0)
				System.out.print(prim[i] + "  ");
		}

	}
}