526互联

质数筛

发布时间 2023-04-06 19:35:54作者: ChuenSan

内容来自 b 站

image-20230405232629443

image-20230405232938819

import java.util.Arrays;
import java.util.Scanner;

public class 质数筛 {
	static int N = 100000010;
	static boolean[] vis = new boolean[N]; // 划掉合数
	static int[] prim = new int[N];// 记录质数
	static int cnt = 0;// 质数个数

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		getPrim(n);
		for (int i=1;i<=cnt;i++) {
			System.out.print(prim[i] + " ");
		}
	}

	static void getPrim(int n) {
		for (int i = 2; i <= n; i++) {
			if (!vis[i]) {
				prim[++cnt] = i;
			}
			for (int j = 1; 1L * i * prim[j] <= n; j++) {// 越界中断
				vis[i * prim[j]] = true;
				if (i % prim[j] == 0) {// 整除中断
					break;
				}
			}
		}
	}
}