868. 筛质数 Java题解 (埃氏筛,线性筛)

2023-11-21 13:40

本文主要是介绍868. 筛质数 Java题解 (埃氏筛,线性筛),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

输入样例:

8

输出样例:

4

解题思路:

埃氏筛质数:又叫朴素筛法,求某个区间的质数个数时,从2开始,将每个数的倍数都筛掉,剩下的数就是质数。缺点:会对某个数重复筛。时间复杂度为O(nlogn)

线性筛法:对埃氏筛的优化,埃氏筛的任意一个数都被它的因数筛了一遍,实际上只需要筛一次就行,即每次只用最小质因子筛,不会被重复筛,时间复杂度为O(nloglogn),非常接近线性。

两种筛法的相同点:都可以在筛选时找到质数的个数,求出区间内的所有质数,并且能求出每个数的最小质因子。

不同点:在10^6内,效率都差不多,但10^7时,线性筛明显比埃氏筛快一倍。

Java代码:(埃氏筛)

import java.io.*;public class Main {public static void main(String[] args) throws NumberFormatException, IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());getPrime(n);}public static void getPrime(int n) {boolean []st = new boolean[n + 1];  // 状态数组,标识是否被筛掉int []primes = new int[n + 1];  // 存放质数int cnt = 0;  //质数的个数for(int i = 2; i <= n; i++) { // 埃氏筛if(!st[i]) primes[cnt++] = i;for(int j = i + i; j <= n; j += i) // 将每个数的倍数都过滤掉,标志为truest[j] = true;}System.out.println(cnt);}
}

Java代码: (线性筛)

import java.io.*public class Main {public static void main(String[] args) throws NumberFormatException, IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());getPrime(n);}public static void getPrime(int n) {boolean []st = new boolean[n + 1];  // 状态数组,标识是否被筛掉int []primes = new int[n + 1];  // 存放质数int cnt = 0;  //质数的个数for(int i = 2; i <= n; i++) {  // 线性筛if(!st[i]) primes[cnt++] = i;for(int j = 0; primes[j] <= n / i; j++) {  //只用最小质因子筛,(筛一次)st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}System.out.println(cnt);}
}

这篇关于868. 筛质数 Java题解 (埃氏筛,线性筛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/402692

相关文章

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

Spring Boot spring-boot-maven-plugin 参数配置详解(最新推荐)

《SpringBootspring-boot-maven-plugin参数配置详解(最新推荐)》文章介绍了SpringBootMaven插件的5个核心目标(repackage、run、start... 目录一 spring-boot-maven-plugin 插件的5个Goals二 应用场景1 重新打包应用

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则:依赖驱动加载手动控制 Bean 加载顺序的方法方法 1:使用@DependsOn(最直

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问