质数筛选

常见方法有：

试除法：

朴素筛法$O(nlogn)$：

埃氏筛法$O(nloglogn)$：

线性筛法$O(n)$：

Java代码模板(朴素筛时间复杂度$O(nlogn)$

import java.util.Scanner;

public class Main {
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		System.out.println(primes(n));
	}
	
    /**
     * 朴素筛法
     */
	static int primes(int n) {
		boolean st[] =  new boolean[n+1]; //用于标记是否不为质数的数字
		int prime[] = new int[n+1]; //用于记录当质数一共有prime[i]个的时候数字为多少
		int ans =0; //记录一共有多少质数
		for(int i=2;i<=n;++i) {
			if(!st[i]) prime[ans++] = i;
			for(int j  = i*2;j<=n;j+=i) {
				st[j] = true;
			}
		}
		return ans;
	}
	
	

}

Javad代码模板(埃氏筛法时间复杂度$O(nloglogn)$，几乎与$O(n)持平$)

import java.util.Scanner;

public class Main {
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		System.out.println(primes(n));
	}
	
	/**
	 * 埃氏筛
	 * @param n
	 * @return
	 */
	static int primes(int n) {
		boolean st[] = new boolean[n+1];
		int prime[] = new int[n+1];
		int ans =0;
		for(int i=2;i<=n;++i) {
			if(!st[i]) {
				prime[ans++] = i;
				for(int j = 2*i;j <=n;j+=i) {
					st[j] = true;
				}
			}
		}
		return ans;
	}
}

Java代码模板(线性筛法时间复杂度$O(n)$)

import java.util.Scanner;

public class Main {
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		System.out.println(primes(n));
	}
	
	
	/**
	 * 线性筛
	 * @param n
	 * @return
	 */
	static int primes(int n) {
		boolean st[] = new boolean[n+1]; //标记数字是否为质数的倍数
		int prime[] = new int[n+1]; //用于存储一共prime[i]个质数时候是数字几
		
		int ans =0;
		for(int i= 2;i<=n;++i) {
			if(!st[i]) prime[ans++] = i;
			for(int j =0;prime[j]<=n/i;++j) {
				st[prime[j]*i] = true;
				if(i%prime[j]==0) break;
			}
		}
		return ans;
	}
}

注意点：

prime[cnt++]=i;这行代码的意思是：如果发现i是素数，那么就把它放进prime数组里，同时把计数器加一。
prime[j]<=n/i;和之前的用法一样，如果pj乘以i的值大于n也没有意义了。
内层for循环要做两件事情，分为两个条件判断：
1.如果i除以prime[j]（简称pj）不等于0，说明pj不是i的最小质因子，并且可以说明pj比i的最小质因子小。这样，pji的最小值因子就一定是pj，我们不管三七二十一，先把pji这个数筛掉。
2.如果i除以pj等于0，说明pj是i的最小质因子，而我们如果继续把j++的话，那么下一个pj就一定不是当前i的最小质因子了，为了避免后面重复计算造成错误，所以这里要break。
综上所述，无论pj能否整除i，pj*i一定是合数，一定要筛掉。