筛选法筛出100以内的素数

﹏ヽ暗。殇╰゛Y 2023-07-18 02:24 113阅读 0赞

## 筛选法筛出100以内的素数 ##

如图（筛选50以内的素数），从第一个素数2开始筛选，2的倍数一定不是素数；以此类推，3的倍数也不是素数。当筛选到4的时候，由于4不是素数，所以可以跳过，继续筛选5的倍数。筛选到什么时候结束呢？为了节省时间开销，筛选到根号50取整就可以结束了，因为一个数n的最大两个因子就是根号n了，其他因子就是一大一小或者一小一大，例如3*5，5*3，3*5已经排出了，那就不需要再判断5*3啦。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJdmUxQW5EMUxlQVJO_size_16_color_FFFFFF_t_70]

#include <stdio.h>
    
    int main()
    { 
    	int i,j,a[100];
    	for(i=0; i<100; i++)
    		a[i]=i+1;
    	for(i=2; i*i<=100; i++)//筛选到根号100
    	{ 
    		if(a[i-1])//如果自身是素数，筛去它的倍数
    		{ 
    			for(j=i*i-1; j<100; j+=i)//这里从它的平方开始找它的倍数，前面的倍数已经筛去
    			{ 
    				if(a[j]!=0)//不是素数就置零
    					a[j]=0;
    			}
    		}
    	}
    	for(i=1; i<100; i++)
    	{ 
    		if(a[i])
    			printf("%d ", a[i]);
    	}
    	printf("\n");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJdmUxQW5EMUxlQVJO_size_16_color_FFFFFF_t_70]: /images/20230528/22a96afc91ee41139eccc3b7e9f90a4f.png

发表评论取消回复

表情：

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

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

相关阅读

相关筛选法筛出100以内的素数

筛选法筛出100以内的素数如图（筛选50以内的素数），从第一个素数2开始筛选，2的倍数一定不是素数；以此类推，3的倍数也不是素数。当筛选到4的时候，由于4不是素数，所以

﹏ヽ暗。殇╰゛Y/ 2023年07月18日 02:24/ 0 赞/ 114 阅读

相关筛选100以内的素数

//筛选100以内的素数 include<stdio.h> include<math.h> int main() { int

待我称王封你为后i/ 2023年07月17日 11:29/ 0 赞/ 174 阅读

相关计算100以内的素数

素数：又叫质数，只能被自己和1整除的数。它的乘因子只有两个。容易理解的计算办法 package com.zhiru; public clas

以你之姓@/ 2022年08月11日 07:29/ 0 赞/ 180 阅读

相关埃式筛法——快速筛选n以内的素数

/ 埃氏筛法（快速筛选n以内素数的个数） / include <bits/stdc++.h> using namespace

╰半夏微凉°/ 2022年06月15日 02:13/ 0 赞/ 266 阅读

相关打印100以内的素数

public class SuShuPrint { public static void main(String[] args) {

忘是亡心i/ 2022年05月15日 00:58/ 0 赞/ 234 阅读

相关打印100以内的素数

public class SuShu { public static void main(String[] args) {

今天药忘吃喽~/ 2022年05月15日 00:38/ 0 赞/ 205 阅读

相关筛选法求100以内的素数

将100个自然数有序排列。第一个数1不是质数也不是合数，不做处理。第二个数2是质数，留下，并把100以内能将2整除的数划掉（置为1）第三个数3是质数，留下，并

桃扇骨/ 2022年05月14日 02:18/ 0 赞/ 236 阅读

相关用简单素数筛选法求N以内的素数

import java.util.Scanner; public class Main \{ public static void main(String\[\] ar

￡神魔★判官ぃ/ 2022年05月04日 20:50/ 0 赞/ 273 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 260 阅读

相关 100以内的质数（素数）

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数 100以内的质数（素数） fun

曾经终败给现在/ 2022年03月15日 19:30/ 0 赞/ 278 阅读