解题思路:
素数的特点:素数乘以任何一个数都能得到一个合数
根据这个特点筛掉N中的合数,剩下的就是素数咯
在座的各位有志青年请看注释!
注意事项:
埃筛法是比较早期的一个纯暴力的改进算法
其实还有一个线性筛,它的效率更高
埃筛用在范围小的数还是很欧克的,
要想判断更大范围的素数还是用线性筛合适!
感兴趣的可以去学习学习!
参考代码:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; import java.util.Stack; /** * @Author:杨雨彤 * @date:2024/1/9 20:42 */ public class daydayone { public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n =Integer.parseInt(br.readLine()); boolean[]isprime=new boolean[n+1];//状态数组 默认false全为素数 int[]prime=new int[n+1];//用来存判断出来的素数,因为事先不知道N内有多少素数,所以初始容量为N int count=0;//用来记录素数的个数,方便后续的遍历 for (int i = 2; i <=n; i++) {//遍历N内的数字 if(!isprime[i]){//如果是素数,这里采用下标和数字对应的关系方便理解,isprime[2]就是数字2的状态 prime[count++]=i;//将数字i添加到素数数组中 for (int j = 2; i*j<=n ; j++) {//拿到一个素数后,开始筛出n内和合数。 isprime[i*j]=true;//素数×任何数(不能×1哦)都是合数,将i*j这个数的isprime[i*j]置为true } } } for (int i = 0; i <count ; i++) {//遍历素数数组 System.out.print(prime[i]); System.out.println(); } } }
0.0分
1 人评分
Tom数 (C++代码)浏览:862 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:640 |
成绩转换 (C语言代码)浏览:1040 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:896 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:1262 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:605 |
Cylinder (C语言描述+详细分析)浏览:3336 |
关于C语言变量位置的问题浏览:291 |
printf基础练习2 (C语言代码)浏览:541 |
C二级辅导-等差数列 (C语言代码)浏览:801 |