首页 > 试题广场 >

求素数

[编程题]求素数
  • 热度指数：3307 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
输入M、N，1 < M < N < 1000000，求区间[M,N]内的所有素数的个数。素数定义：除了1以外，只能被1和自己整除的自然数称为素数

输入描述:
两个整数M，N


输出描述:
区间内素数的个数
示例1

输入

2 10

输出

4
算法知识视频讲解
添加回答
Java
coffeemao头像 coffeemao
// 这个题自测有问题，自己输入2 10 正确答案是4，他给人报错为2
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();
//        System.out.println(violence(start,end));
//         System.out.println(violence2(start,end));
         System.out.println(ethiopia(start,end));
    }
    /**
     * 方法一、暴力破解法-1
     * 从起始数开始循环到终止数，2~当前数-1，不可整除为素数
     * 是进行count++
     * 结果为：超时，算法复杂度过大
     * */
    private static int violence(int start,int end){
        int count = 0;
        for (int i = start; i < end; i++) {
            if (i == 2){
                count++;
            }
            for (int j = start; j < i; j++) {
                if (i%j == 0){
                    break;
                }
                if (j == i-1)
                    count++;
            }
        }
        return count;
    }
    /**
     * 方法二、暴力破解法-2
     * 从起始数开始循环到终止数，设boolean标志，判断当前数是否是素数
     * 是进行count++
     * */
    private static int violence2(int start,int end){
        int count = 0;
        for (int i = start; i < end; i++) {
            count += isPrime(i) ? 1 : 0;
        }
        return count;
    }

    private static boolean isPrime(int i) {
        for (int j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0){
                return false;
            }
        }
        return true;
    }
    /**
     * 方法三、埃塞法
     * 初始化标志位boolean数组，全为false 代表是素数
     * 先判断一下,flag 为false 代表素数，count++
     * 素数的倍数都不是素数，将其标志为 true
     * */
    private static int ethiopia(int start,int end){
        int count = 0;
        boolean[] flag = new boolean[end];

        for (int i = start; i < end; i++) {
            if (!flag[i]){
                count++;
                // System.out.println(i);
                // 注意：在使用 j = i * i 可减少查找次数，但容易造成数组越界
                for (int j = i * 2; j < end; j+=i) {
                    flag[j] = true;
                }
            }
        }
        return count;
    }
    
}

发表于 2022-01-24 12:55:02 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 模拟 前端工程师 算法工程师 吉比特 2018 PHP工程师 Java工程师
上传者：小小
难度：
1条回答 4464浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号