题解 | #判断素数个数#

判断素数个数

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的素数"); //输出
    }
}

全部评论

相关推荐

在评审的大师兄很完美:像这种一般就是部门不匹配 转移至其他部门然后挂掉 我就是这样被挂了
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务