下载文档原格式
例6、用筛法求出100以内的全部素数，并按每行五个数显示。
【问题分析】⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0；⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N)) 为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。
用筛法求素数的过程示意如下（图中用下划线作删去标志）：① 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 ｛置数｝② 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被2整除的数}③ 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被3整除的数}……2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被整除的数}Program Exam53;const N=100;type xx=1 .. N; {自定义子界类型xx（类型名）}Var a: array[xx] of boolean; i,j: integer;BeginFillchar(a,sizeof(a),true);a[1] := False;for i:=2 to Trunc(sqrt(N)) doif a[I] thenfor j := 2 to N div I doa[I*j]:= False;t:=0;for i:=2 to N doif a[i] thenBeginwrite(a[ i ]:5); inc(t);if t mod 5=0 then writelnend;End.【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法）分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。
埃塞法求素数什么是素数？素数是指大于1且只能被1和自身整除的整数。
例如，2、3、5、7、11等都是素数，而4、6、8、9等则不是素数。
素数在数论中具有重要的地位，它们的特殊性质使得它们在密码学、计算机科学等领域有广泛的应用。
埃塞法（筛法）是什么？埃塞法，又称筛法，是一种用于求解素数的算法。
它的基本思想是通过逐步筛除合数的方法，找出一定范围内的所有素数。
埃塞法的步骤1.首先，我们需要确定一个范围，假设为n。
2.创建一个长度为n+1的布尔数组，初始值都为True。
这个数组用来表示数字是否为素数，索引对应的数字为素数则对应的值为True，否则为False。
3.从2开始，将数组中索引为2的倍数的值设置为False，因为2的倍数肯定不是素数。
4.接下来，找到第一个为True的索引值，假设为p，这个值就是我们找到的第一个素数。
5.然后，将数组中索引为p的倍数的值设置为False，因为p的倍数肯定不是素数。
6.重复步骤4和5，直到找不到下一个为True的索引值。
7.最后，数组中为True的索引值就是范围内的所有素数。
一个简单的埃塞法求素数的实现（Python）下面是一个简单的Python代码示例，用于实现埃塞法求素数：def sieve_of_eratosthenes(n):primes = [True] * (n+1)primes[0] = primes[1] = Falsep = 2while p * p <= n:if primes[p]:for i in range(p * p, n+1, p):primes[i] = Falsep += 1result = []for i in range(2, n+1):if primes[i]:result.append(i)return resultn = int(input("请输入一个正整数n："))primes = sieve_of_eratosthenes(n)print("范围内的素数有：", primes)示例说明在上述示例中，我们首先定义了一个名为sieve_of_eratosthenes的函数，它接受一个正整数n作为参数，返回范围内的所有素数。
C 使用筛选法求100以内的素数C++使用筛选法求100以内的素数，具体问题分析及其代码如下：【问题分析】我们可以把100个数看作是沙子和石子，素数是石子，非素数的是沙子，弄个筛子，将沙子筛掉，剩下的就是素数。
1至100这些自然数可以分为三类：(1) 单位数：仅有一个数1.(2) 素数：这个数大于1，且只有它本身和1这样两个正因数。
(3) 合数：除了1和他自身以外，还有其他的正因数。
【代码如下】/********************************************************/* 程序名：素数筛选/* 编程时间：2009年7月27日/* 主要功能：求素数*********************************************************/#include<iostream>using namespace std;//编译命令#include<math.h>const int MAX=100;//定义常量MAXint main()//主函数{int prime[MAX+100]={0};//定义变量并初始化int i,j,k=sqrt(MAX);for(i=2; i<=k; i++)//枚举筛数{if(prime[i]==0)//如果这个数没被筛，就看看{j=i*2;//将原数扩大二倍初始化给jdo{prime[j]=1;//将j筛掉j+=i; //再扩大一倍}while(j<=MAX);//直到最大}}for(i=2; i<=MAX; i++){if(prime[i]==0)//循环输出cout<<i<<" ";}cout<<endl;return 0;//主函数结束}【运行结果】。
筛选法求素数c语言一、什么是素数？素数，又称质数，是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。
比如2、3、5、7、11等都是素数。
二、为什么要求素数？在计算机科学中，素数有着重要的应用。
比如在加密算法中，RSA算法就是基于大质数的分解来实现加密和解密的。
此外，在计算机图形学中也常常用到素数。
三、筛选法求素数筛选法求素数是一种简单而有效的方法。
它的基本思想是：先把从2开始的各个自然数列出来，然后按照从小到大的顺序对每个未标记过的最小质数p进行标记，并把p的倍数标记成合数。
重复这个过程直到所有数字都被标记。
具体实现上可以使用一个布尔数组isPrime[]来表示每个数字是否为质数。
初始时将所有元素赋值为true（即都认为是质数），然后从2开始遍历数组，如果当前元素isPrime[i]为true，则说明i是一个质数，并将i的倍数isPrime[i*j]（j=2,3,4...）全部标记成false（即合数）。
这样遍历完整个数组后，isPrime[]为true的元素就是所有的质数。
四、C语言代码实现下面是一个基于筛选法求素数的C语言代码实现：```c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>void sieveOfEratosthenes(int n) {bool isPrime[n+1];for (int i = 2; i <= n; i++) {isPrime[i] = true;}for (int i = 2; i*i <= n; i++) {if (isPrime[i]) {for (int j = i*i; j <= n; j += i) {isPrime[j] = false;}}}printf("The prime numbers between 2 and %d are:\n", n);for (int i = 2; i <= n; i++) {if (isPrime[i]) {printf("%d ", i);}}}int main() {int n;printf("Enter a number: ");scanf("%d", &n);sieveOfEratosthenes(n);return 0;}```五、代码解析首先定义了一个函数sieveOfEratosthenes，它的参数n表示要求解的范围。
例6、用筛法求出100以内的全部素数，并按每行五个数显示。
【问题分析】⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0；⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N)) 为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。
用筛法求素数的过程示意如下（图中用下划线作删去标志）：①2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 ｛置数｝②2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被2整除的数}③2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被3整除的数}……2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被整除的数}Program Exam53;const N=100;type xx=1 .. N; {自定义子界类型xx（类型名）}V ar a: array[xx] of boolean; i,j: integer;BeginFillchar(a,sizeof(a),true);a[1] := False;for i:=2 to Trunc(sqrt(N)) doif a[I] thenfor j := 2 to N div I doa[I*j]:= False;t:=0;for i:=2 to N doif a[i] thenBeginwrite(a[ i ]:5); inc(t);if t mod 5=0 then writelnend;End.【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法）分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。
素数快速筛法及公式素数快速筛法及公式梅生林安徽合肥2012.07.12摘要：在素数的研究中，总结出素数快速筛法及公式，在这个基础上扩展了素数的一些关系、性质。
关键词：素数快速筛法，素数通式，质数筛法公式1.引言素数（Prime Number）是指自然数中那些只能被1和本身整除的数，依次为2、3、5、7、11、13、17、19、23、29…。
前人已证明：素数有无限多个。
一直到现在人们判定、寻找素数的方法，还是古希腊的数学家艾拉托斯芬（Eratosthenes）提出过的筛式方法，简称“艾氏筛法”。
即在任意有限自然数N以内判定素数时，先把N一个不漏的写下来，然后划掉根号N（）内所有素数的倍数，我们就能得到N以内的全部素数。
艾氏筛法判定素数的过程机械，也未能表示素数公式和一些性质。
关于寻找判定表示素数的方法公式，以前众多数学家进行了艰辛探索，也提出了很多关于素数的猜想和问题。
欧拉(Euler)就提出二项式公式n2-n+41能生成一部分素数的数型公式，直到现在，素数研究中仍然还有许多未解问题。
本文通过素数快速筛法及公式，总结出一些素数的新理论，使素数筛法及公式等都将是一次质变，将为素数研究抛砖引玉，也可能为数论增添上新的一页。
2.素数的快速筛法原理及公式当我们用艾氏筛法是要划掉每个合数，只2的倍数就差不多要划掉一半自然数，越往后面合数越多，而留下的素数越少。
我们能不能利用数学原理、公式去掉大部分合数呢？答案是肯定的。
2.1 当我们想去掉第一个素数2的倍数时，我们可能会想到用：2N+1 （N≥1）N为大于等于1的自然数，以下公式同上。
2.2 去掉2、3的倍数时，用2*3的倍数加上同为2、3互质的数：6N±12.3 去掉2、3、5的倍数时，用2*3*5的倍数加上同为2、3、5互质的数：30N±1，30N±7，30N±11，30N±13，2.4 去掉2、3、5、7的倍数时，同上的方法：210N±1，210N±11，210N±13，210N±17，210N±19，210N±23，210N±29，210N±31，210N±37，210N±41，210N±43，210N±47，210N±53，210N±59，210N±61，210N±67，210N±71，210N±73，210N±79，210N±83，210N±89，210N±97，210N±101，210N±103，2.5 去掉2、3、5、7、11的倍数时，同上的方法：2310N±1，2310N±13，2310N±17，2310N±19，……2310N±1139，2310N±1147，2310N±1151，2310N±1153，我们可以一直做下去，就会去掉从前面开始的素数倍数，划掉的合数比例将越来越少。
1. 用筛法求100以内的素数。
算法：先将1~100放置于一个一维数组中，然后依次判断每个数是否素数，若不是素数将该元素置0，最后输出不为0的数。
如何判断一个数是否素数？素数定义是只能被1和本身整除的数，设置除数n=2~a[i]-1特殊的两个数1、2，不需要判断定义变量：int a[100]，i，n；输入数据：循环赋值，for(i=0;i<100;i++) a[i]=i+1;处理：双重循环，外层循环控制访问数组元素，内层循环控制除数的变化for(i=2;i<100;i++) for(n=2;n<=a[i]/2;n++) if(a[i]%n==0) a[i]=0；输出：for（i=0；i<100;i++）if(a[i]!=0) printf(“%3d”,a[i]);2. 编写一个程序，计算若干学生的某门功课的平均成绩、标准差，找出最高分和最低分。
算法：循环输入成绩，需要求和，然后求平均成绩；循环sqrt（求和（xi-aver）*（xi-aver））定义变量：float grade[N]，max，min，aver，bzc，sum；int i；输入数据：for(i=0;i<N;i++) scanf(“%f”,&grade[i]);处理：sum=0; max=min=grade[0];for(i=0;i<N;i++) {sum=sum+grade[i];if(max<grade[i]) max=grade[i]; if(min>grade[i]) min=grade[i];}aver=sum/N;sum=0; for(i=0;i<N;i++) sum=sum+(grade[i]-aver)* (grade[i]-aver);bzc=sqrt(sum/N);输出结果3.编写一个程序，让计算机产生20个随机数，用选择法排序。
98 36 54 18 65 23 48 78 84 8for(i=0;i<N-1;i++){p=i；for(j=i+1;j<N;j++) if(a[p]>a[j]) p=j;if(p!=i) { t=a[p];a[p]=a[i];a[i]=t;}}设置一个变量p，去记住最小值的下标，4. 根据上题的内容1，编一程序在数组中查找一个数。
1）要将“China”译成密码，密码规律是：用原来的字母后面第4个字母替原来的字母。
例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。
因此，“China”应译为“Glmre”。
请编一程序，用赋初值的方法使c1、c2、c3、c4、c5五个变量的值分别为‘C’，‘h’、‘i’、‘n’、‘a’，经过运算，使分别变为‘G’，‘l’，‘m’，‘r’、‘e’，并输出。
2）给出一百分制成绩，要求输出成绩等级‘A’、‘B’、‘C’、‘D’、‘E’，90分以上为‘A’，80—89分为‘B’，70—79分为‘B’，60—69分为‘B’，60分以下为‘E’3）给出一个不多于5位的正整数，要求：1、求出它是几位数；2、分别打印出每一位数字；3、按逆序打印出个位数字，例如原数是321，应输出123。
4）输入4个整数，要求按由小到大的顺序输出。
5）企业发放的奖金根据利润提成。
数组6）用筛选法求100之内的素数7）用选择法对10个整数排序8）求一个3*3的整型矩形对角线元素之和9）已有一个已排好序的数组，今输入一个数，要求按原来排序的规律将它插入数组中10）将一个数组中的值按逆序重新存放。
11）打印魔方阵。
行，列，对角线和相等12）找出一个二维数组的鞍点，该行最大，该列最小，也可能没有。
13）有15个数按由大到小存放，用折半法找出该数是数组中第几个元素的值。
14）电文加密15）字符串连接16）字符串比较17）字符串拷贝函数18）写两个函数，分别求两个整数的最大公约数和最小公倍数19）写一个判素数的函数20）写一个函数，使一个给定的二维数组行列互换21）写一个函数，使字符串反序存放，在主函数中输入输出22）写一函数，将一个字符串中元音字母复制到另一字符串23）写一函数，输入一个4位数字，要求输出4个数字字符，但要求数字间空一个空格24）编写一个函数，统计参数字符串中字母、数字、空格和其他字符的个数25）写一个函数，输入一行字符，将此字符串最长的单词输出26）写一函数，用起泡法对10个字符排序27）输入10个学生5门课的成绩，分别用函数求：每个学生的平均分，每门课的平均分，找出最高分数对应的学生和课程，28）写几个函数，输入10个职工的姓名和职工号，按职工号从大到小的顺序排序，姓名顺序也随着调整；用折半法查找输入的一个职工号，输出该职工姓名。
1、用筛选法求100之内的素数。
#include <stdio.h>void main(){int num[100],i,j;for (i=0;i<100;i++) num[i]=1;for (i=2;i<=10;i++)for (j=2;i*j<=100;j++) num[i*j-1]=0;printf("0至100内素数有:\n");for (i=j=0;i<100;i++)if (num[i]==1) {printf("%-4d",i+1);if (++j%4==0) printf("\n");}}2、用选择法对10个整数排序。
#include <stdio.h>void main(){int num[10],n,i,j,t,k;printf("请输入十个整数:");for (n=0;n<10;n++) scanf("%d",&num[n]);for (i=0;i<9;i++){k=i;for (j=i+1;j<10;j++)if (num[k]<num[j]) k=j;if (k!=i) {t=num[i];num[i]=num[k];num[k]=t;}}printf("从大到小排序为:");for (n=0;n<10;n++) printf("%d ",num[n]);}3、求一个3*3的整型二维数组对角线元素之和。
#include <stdio.h>void main(){int num[3][3],i,j;printf("输入二维数组:\n");for (i=0;i<3;i++)for (j=0;j<3;j++)scanf("%d",&num[i][j]);printf("两对角线和分别为%d 和%d\n",num[0][0]+num[1][1]+num[2][2],num[0][2]+num[1][1]+num[2][0]);}5、将一个数组中的值按逆序重新存放。
素数筛选法欧拉筛选法素数筛选法是一种用于快速找出一定范围内的素数的算法。
该算法的基本思想是从小到大依次遍历所有数，将其所有的倍数标记为合数，剩下的未被标记的数即为素数。
欧拉筛选法是一种改进的素数筛选法，其核心思想是对每个数仅标记它的最小质因数，并同时处理掉其所有的合数。
这样，每个合数都会被它的最小质因数筛掉，避免了重复标记的问题，提高了效率。
欧拉筛选法的具体步骤如下：1. 初始化一个布尔数组is_prime，大小为n+1，is_prime[i]表示数i是否为素数。
2. 初始化一个整数数组prime，用于存储筛选得到的素数。
3. 遍历2到n的每个数i：- 如果is_prime[i]为true，则将i加入prime数组，并将i的最小质因数设为i。
- 遍历prime数组中的素数p：- 如果i * p大于n，则退出循环。
- 将i * p标记为合数，并将其最小质因数设为p。
- 如果i能整除p，即i是p的最小质因数，退出循环。
4. 返回prime数组中的素数。
欧拉筛选法相较于传统的素数筛选法，在时间复杂度上有所提升。
原因在于，欧拉筛选法避免了对每个数重复标记合数的步骤，并且使用了最小质因数将每个合数筛掉，避免了重复工作。
对于欧拉筛选法的优化，还可以进一步使用升序遍历质数的方法，即i从小到大遍历时，除数p也按从小到大的顺序遍历。
这样能够进一步提高效率，因为对于每个数i，i * p最早被标记为合数的因子p一定是i的最小质因数。
通过欧拉筛选法可以快速得到一定范围内的素数，并且可以处理大范围的素数筛选。
素数在很多领域中都有重要应用，比如密码学、算法设计等。
因此，欧拉筛选法是一种非常实用和高效的算法。
总结起来，欧拉筛选法是一种基于素数筛选的算法，通过优化标记合数和使用最小质因数的方法，能够更加高效地找出一定范围内的素数。
该算法的特点是简单易懂、实现方便，使用广泛，并且在时间复杂度上有所提升。
这使得欧拉筛选法成为一种常用的素数筛选算法，对于解题和算法设计具有重要意义。
⽤筛选法求100以内的素数（筛选法）#include<stdio.h>
#include<math.h>
int main()
{
int a[101],i,j;
for(i=1; i<=100; i++)
{
a[i] = i; //为数组赋初值
}
a[1] = 0;//先去掉a[1]
for(i=2; i<sqrt(100); i++) //如果需要找1-n范围内的素数表，只须进⾏到除数为根号下n（取整数就可）
{
for(j=i+1; j<=100; j++)
if( a[i]!=0 && a[j]!=0 )
if(a[j]%a[i] == 0)
{
a[j] = 0;
}
}
printf("\n");
int n;
for(i=2,n=0; i<=100; i++)
{
if(a[i]!=0)
{
printf("%5d",a[i]);
n++;
}
if(n==10)
{
printf("\n");
n = 0;//⼀次完成之后初始化
}
}
return0;
}
所谓筛选法是“埃拉托⾊尼筛法“，将⼀组数据逐个判断他们是否素数，找出⼀个⾮素数，就把它挖掉，最后剩下的就是素数算法可表⽰为；
（1）挖去1；
（2）⽤下⼀个未被挖去的数p除p后⾯各数，把p的倍数挖掉
（3）检查p是否⼩于根号n的整数部分，如果是，则返回（2）继续执⾏，否则就结束
（4）剩下的就是素数。
c++⽤筛法求100之内素数。
1、⽤筛法求100之内素数。
相关知识：⽤筛法求素数的基本思想是：把从1开始的、某⼀范围内的正整数从⼩到⼤顺序排列， 1不是素数，⾸先把它筛掉。
剩下的数中选择最⼩的数是素数，然后去掉它的倍数。
依次类推，直到筛⼦为空时结束。
如有：1234567891011121314151617181920212223242526272829301不是素数，去掉。
剩下的数中2最⼩，是素数，去掉2的倍数，余下的数是：357911131517192123252729剩下的数中3最⼩，是素数，去掉3的倍数，如此下去直到所有的数都被筛完编程要求：根据提⽰，在右侧编辑器补充代码，输出100以内所有素数。
预期输出：2357111317192329313741434753596167717379838997程序源码：#include <iostream>#include <iomanip>using namespace std;#include <math.h>int main(){// 请在此添加代码/********** Begin *********/int count=0,susu=1;for(int i=2;i<100;i++){for(int j=2;j<=i/2;j++) //只需要循环到原本数的⼀半即可{if(i%j==0){susu=0;break;}}if(susu){printf("%5d ",i);count++;if(count==10) //输出10个数就换⾏{count=0;printf("\n");}}susu=1;}/********** End **********/return0;}。
埃拉托斯特尼筛法求素数
埃拉托斯特尼筛法，又称埃氏筛法，是一种由古希腊数学家埃拉齐斯·埃拉托斯特尼发现
的求素数的方法，是素数筛选的一种算法。
埃拉托斯特尼筛法的原理非常简单，要求求出从2开始至某一数之间的全部素数：
首先，将2~N的各数列出来，把2留下，其余全部标记为可以被删去；
其次，将2这个数的倍数全部删去，3留下，其余全部标记为可以被删去；
再次，将3这个数的倍数全部删去，5留下，其余全部标记为可以被删去；
以此类推，将后面所有留下来的数的倍数全部删去，最后剩下来的就是不被其他数整除的数，也就是素数。
优点：埃拉托斯特尼筛法的实现比较容易，消耗的计算资源很少。
它的平均时间复杂度是
O(NloglogN)，主要分为把N内的数列出来，把N之内的素数筛选出来两个步骤，把N内
的数列出来
它只需要多次循环，每次把一个数的倍数筛除掉，就能求出一定范围范围内的所有素数，
因此一个与这个时间复杂度十分接近的算法就得到了，运行起来也分显迅速。
缺点：由于这种算法仅仅在某种领域有效，所以不适合多用于多种情况，而且它的时间复
杂度比较高，它要求算法的计算效率有较高的要求，较其他算法程序相比，埃拉托斯特尼
算法的计算时间比较长。
对于程序实现来说，埃拉托斯特尼筛法也需要考虑嵌套和循环方面的知识，并且计算复杂
度高，容易引起算法程序的运行变慢的问题。
总的来说，埃拉托斯特尼筛法是一种很简单的算法，但却有很高的效率，在数学上有着独
特的含义，能使素数筛选算法的计算效率大大的提升，可以说是一个重要的优化筛选算法。
欧拉筛选素数法c++全文共四篇示例，供读者参考第一篇示例：欧拉筛选素数法是一种高效的算法，用于在一定范围内快速筛选出所有的素数。
它是由瑞士数学家欧拉所提出的，因此得名欧拉筛选素数法。
在本篇文章中，我们将介绍欧拉筛选素数法的原理和实现方法，并附上一个简单的C++代码示例。
欧拉筛选素数法的原理是利用筛法的思想，从2开始不断地筛选掉合数，最终剩下的就是素数。
相比传统的试除法，欧拉筛选素数法在复杂度上有着明显的优势，可以更快地找到素数。
下面是欧拉筛选素数法的具体步骤：1. 初始化一个bool类型的数组prime[]，全部初始化为true。
2. 从2开始遍历到n，如果prime[i]为true，则将i的所有倍数i*j （其中j>=2）标记为false。
3. 遍历完毕后，prime[i]为true的i就是素数。
接下来，我们将通过一个简单的C++代码示例来演示欧拉筛选素数法的实现：```cpp#include <iostream>#include <vector>using namespace std;void eulerSieve(int n) {vector<bool> prime(n+1, true);for(int i=2; i<=n; i++) {if(prime[i]) {cout << i << " ";for(int j=2; i*j<=n; j++) {prime[i*j] = false;}}}}欧拉筛选素数法的时间复杂度为O(nloglogn)，具有很高的效率。
在需要求解一定范围内的素数时，欧拉筛选素数法是一个很好的选择。
欧拉筛选素数法是一种简单而高效的算法，可以在较短的时间内找到指定范围内的素数。
通过本文的介绍和示例代码，相信读者对欧拉筛选素数法有了更深入的了解，并可以在实际应用中灵活运用。
用筛选法求100以内素数素数又称质数，是大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
100以内的素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。
素数的概念可以追溯到古希腊时期，当时的数学家们就已经开始研究素数的性质，并发现了一些有趣的结论。
素数的概念在数学中十分重要，它们在计算机科学、密码学、编码理论等领域都有着重要的应用。
要求求出100以内的素数，可以使用筛选法。
筛选法的基本思想是：从2开始，将2的倍数剔除掉，然后再从下一个未被剔除的数开始，将它的倍数剔除掉，依次类推，直到100以内的所有数都被剔除掉，剩下的就是素数。
首先，从2开始，将2的倍数剔除掉，即4、6、8、10、12、14、16、18、20、22、24、26、28、30、32、34、36、38、40、42、44、46、48、50、52、54、56、58、60、62、64、66、68、70、72、74、76、78、80、82、84、86、88、90、92、94、96、98、100，剩下的数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。
接下来，从3开始，将3的倍数剔除掉，即6、9、12、15、18、21、24、27、30、33、36、39、42、45、48、51、54、57、60、63、66、69、72、75、78、81、84、87、90、93、96、99，剩下的数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。
依次类推，从4开始，将4的倍数剔除掉，即8、12、16、20、24、28、32、36、40、44、48、52、56、60、64、68、72、76、80、84、88、92、96、100，剩下的数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。
⽤筛选法求100之内的素数1. ⽤筛选法求100之内的素数【答案解析】素数：约数为1和该数本⾝的数字称为素数，即质数筛选法：⼜称为筛法。
先把N个⾃然数按次序排列起来。
1不是质数，也不是合数，要划去。
第⼆个数2是质数留下来，⽽把2后⾯所有能被2整除的数都划去。
2后⾯第⼀个没划去的数是3，把3留下，再把3后⾯所有能被3整除的数都划去。
3后⾯第⼀个没划去的数是5，把5留下，再把5后⾯所有能被5整除的数都划去。
这样⼀直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
因为希腊⼈是把数写在涂腊的板上，每要划去⼀个数，就在上⾯记以⼩点，寻求质数的⼯作完毕后，这许多⼩点就像⼀个筛⼦，所以就把埃拉托斯特尼的⽅法叫做“埃拉托斯特尼筛”，简称“筛法”。
（另⼀种解释是当时的数写在纸草上，每要划去⼀个数，就把这个数挖去，寻求质数的⼯作完毕后，这许多⼩洞就像⼀个筛⼦。
）【代码实现】//⽤筛选法求100以内的素数#include<stdio.h>int main(){int i, j, k = 0;// 将数组汇总每个元素设置为：1~100int a[100];for (i = 0; i < 100; i++)a[i] = i+1;// 因为1不是素数，把a[0]⽤0标记// 最后⼀个位置数字是100，100不是素数，因此循环可以少循环⼀次a[0] = 0;for (i = 0; i < 99; i++){// ⽤a[i]位置的数字去模i位置之后的所有数据// 如果能够整除则⼀定不是素数，该位置数据⽤0填充for (j = i + 1; j < 100; j++){if (a[i] != 0 && a[j] != 0){//把不是素数的都赋值为0if (a[j] % a[i] == 0)a[j] = 0;}}}printf(" 筛选法求出100以内的素数为：\n");for (i = 0; i < 100; i++){//数组中不为0的数即为素数if (a[i] != 0)printf("%3d", a[i]);}printf("\n");return 0;}【运⾏结果】。
