求素数

╰+哭是因爲堅強的太久メ 2021-09-15 05:02 383阅读 0赞

素数：

在大于1的整数中，只能被1和这个数本身整除的数，如2、3、5、7、11。也叫质数。

求0-n之间所有的素数。

测试用例：20

2 3 5 7 11 13 17 19

步骤：

1、把2到n的自然数放入a\[2\]到a\[n\]中(所放入的数与下标号相同) ;

2、在数组元素中以下标为序，按顺序找到未曾找过的最小素数minp和它的位置p(即下标号);

3、从p+1开始，把凡是能被minp整除的各元素值从a数组中划去(筛掉)，也就是把该元素标记为0;

4、让p=p+1，重复执行第(2) (3)步骤，知道，minp>floor(sqrt(n))为止;

5、打印输出a数组中留下来的数，未被筛掉的各元素值;

步骤参考：https://blog.csdn.net/yangyuhao0408/article/details/50956143

java代码实现如下：

import java.util.Scanner;
    
    public class Test8 {
    
    	public static void main(String[] args) {
    		
    		Scanner in=new Scanner(System.in);
    		int n=in.nextInt();
    		boolean[] a=new boolean[n+1];
    		for(int i=0;i<=n;i++){
    			a[i]=true;
    		}
    		a[1]=false;
    		
    		for(int i=2;i<Math.sqrt(n);i++){
    			if(a[i]){
    				for(int j=2;j<=n/i;j++){
    					a[i*j]=false;
    				}
    			}
    		}
    		for(int i=2;i<=n;i++){
    			if(a[i]){
    				System.out.print(i+" ");
    			}
    		}
    		
    	}
    
    }

运行结果为：

> ![20180410112948626][]  
>

[20180410112948626]: /images/20210720/916e4240aec5469d83204ebc2a6beb57.png

发表评论取消回复

表情：

评论列表（有 0 条评论，383人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python－求素数序列

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.cap

刺骨的言语ヽ痛彻心扉/ 2022年12月25日 10:53/ 0 赞/ 141 阅读

相关求素数

求素数 Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述求小于n的所有素数的数量。输入

た入场券/ 2022年08月10日 04:58/ 0 赞/ 177 阅读

相关【C语言】求素数

/ 求素数 / include <stdio.h> int prime(int num) { int i = 2;//素数能被1整除

ゝ一纸荒年。/ 2022年06月12日 05:27/ 0 赞/ 223 阅读

相关求素数（普通+筛选）

一般求解n以内素数的算法。时间复杂度是o(n\sqrt(n)),当n较小时可以用。代码： ![Center][] 当n较大时，一般选用埃氏筛选法，时间复杂度o(n

逃离我推掉我的手/ 2022年06月11日 08:23/ 0 赞/ 226 阅读

相关 c语言求素数

include <stdio.h> include <stdlib.h> / run this program using the conso

妖狐艹你老母/ 2022年06月07日 10:40/ 0 赞/ 258 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 262 阅读

相关 Delphi 求素数

GUI界面： ![2018111711484825.png][] 源代码： unit Unit1; interface

àì夳堔傛蜴生んèń/ 2022年04月16日 05:09/ 0 赞/ 221 阅读

相关筛选法求素数

int vis[1000]; //记录标记 int p[1000]; //存素数 int main() { int n,i

系统管理员/ 2022年03月10日 07:45/ 0 赞/ 306 阅读

相关求素数

\include<stdio.h> \include<math.h> int prime(int m); int main(void) \{ int co

傷城~/ 2021年11月09日 23:46/ 0 赞/ 319 阅读

相关求素数

素数：在大于1的整数中，只能被1和这个数本身整除的数，如2、3、5、7、11。也叫质数。求0-n之间所有的素数。测试用例：20

╰+哭是因爲堅強的太久メ/ 2021年09月15日 05:02/ 0 赞/ 384 阅读