题解 | #判断素数个数#
判断素数个数
https://www.nowcoder.com/practice/c6ad83181a17408eb7605d51a251dd9a
import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int start = scanner.nextInt(); int end = scanner.nextInt(); method(start, end); } public static int prime_Between(int start, int end) { //其实用hashset就行,第二个参数没用到懒得改 HashMap<Integer, Boolean> isPrime = new HashMap<>(); for (int i = 2; i <= end; i++) { if (!isPrime.containsKey(i)) { //筛选法,设置num1是为了从大于等于start的数直接开始比较,速度快 int num1 = (int) Math.ceil(1.0 * start / i); int multiplier = Math.max(2, num1); while (i * multiplier <= end ) { //未添加过的添加进去,防止重复计数 if (!isPrime.containsKey(i * multiplier)) { isPrime.put(i * multiplier, false); } multiplier++; } } } if (end <= 2) { return 0; } else { //将【Math.max(start, 3),end】区间内总数减去非素数即可得到大于2的素数 return end - Math.max(start, 3) + 1 - isPrime.size(); } } public static void method(int start, int end) { int count; if (start > end) { //如果start更大,则交换 int temp = start; start = end; end = temp; } count = prime_Between(start, end); System.out.println(start + "到" + end + "之间有" + count + "个大于2的素数"); //输出 } }