编写程序，使用筛选法求解并打印出小于n（设n为100）的所有素数。

### 回答1： 筛选法是一种常见的求解小于n的所有素数的方法。具体步骤如下： 1. 创建一个长度为n的布尔数组，初始值全部为true。 2. 从2开始，将2的倍数、3的倍数、4的倍数……全部标记为false。 3. 找到下一个未被标记为false的数，将它的倍数全部标记为false。 4. 重复步骤3，直到找不到未被标记为false的数。 5. 最后，数组中所有值为true的下标就是小于n的所有素数。 下面是一个使用筛选法求解小于n的所有素数的Python程序： ```python def sieve(n): is_prime = [True] * n is_prime[] = is_prime[1] = False for i in range(2, int(n ** .5) + 1): if is_prime[i]: for j in range(i * i, n, i): is_prime[j] = False return [i for i in range(n) if is_prime[i]] ``` 这个程序中，首先创建一个长度为n的布尔数组is_prime，初始值全部为True。然后从2开始，将2的倍数、3的倍数、4的倍数……全部标记为False。接着找到下一个未被标记为False的数，将它的倍数全部标记为False。重复这个过程，直到找不到未被标记为False的数。最后，数组中所有值为True的下标就是小于n的所有素数。 最后，程序使用列表推导式，将数组中所有值为True的下标转换为小于n的所有素数，并返回结果。 ### 回答2： 筛选法是一种常见的求解小于n的素数的算法，它的基本思想是从2开始，依次将小于n的整数的倍数去掉，剩下的即为素数。 为了实现筛选法，我们需要先定义一个布尔数组，用来存储小于n的整数是否为素数，然后初始化数组，将所有元素都设为true。接着，从2开始遍历整个数组，如果某个数为素数，则将它的倍数设置为false，直到遍历到n的平方根为止，最后遍历整个数组，将所有为true的下标输出，即为小于n的所有素数。 下面是使用C++语言实现的筛选法求解小于n的素数代码： ```c++ #include<iostream> #include<cstring> #include<cmath> using namespace std; int main(){ const int N=1000001; //定义数组长度 bool isPrime[N]; //定义布尔数组 memset(isPrime,true,sizeof(isPrime)); //初始化所有元素为true int n; cin>>n; //输入n for(int i=2;i<=sqrt(n);i++){ //从2遍历到n的平方根 if(isPrime[i]){ //如果i为素数 for(int j=i*i;j<=n;j+=i){ //将所有i的倍数都设置为false isPrime[j]=false; } } } for(int i=2;i<=n;i++){ //遍历整个数组 if(isPrime[i]){ //输出所有为true的下标 cout<<i<<" "; } } return 0; } ``` 以上就是使用筛选法求解小于n的所有素数的实现方法。这种算法虽然时间复杂度为O(nloglogn)，相对较优，但当n非常大时，仍可能出现效率较低的情况。因此在实际应用中，需要根据具体场景选择更为适合的求解素数的算法。 ### 回答3： 筛选法是求解素数的一种高效算法。它的基本思路是从小到大遍历整数序列，将能够被已知的质数整除的数去除掉，剩下的数就是素数。 具体实现过程如下： 首先定义一个长度为n的布尔数组prime，用来标识每个数是否为素数。把prime数组全部初始化为true，表示所有的数都是素数。 从2开始遍历到n，对于每个数i，如果prime[i]仍然为true，就将i标记为素数，并将i的倍数全部标记为false。这里需要注意的是，标记i的倍数时，从i*i开始标记，因为小于i*i的倍数在之前已经被标记过了。 遍历完成之后，prime数组中所有值为true的下标对应的数就是小于n的所有素数。 下面是使用C++语言实现筛选法求解小于n的素数的代码： ```c++ #include <iostream> #include <vector> using namespace std; void findPrimes(int n) { vector<bool> prime(n + 1, true); // 初始化为true for (int i = 2; i * i <= n; i++) { if (prime[i]) { // 若i是素数，则将所有i的倍数标记为合数 for (int j = i * i; j <= n; j += i) { prime[j] = false; } } } // 输出所有素数 for (int i = 2; i <= n; i++) { if (prime[i]) { cout << i << " "; } } } int main() { int n; cin >> n; findPrimes(n); return 0; } ``` 例如，如果输入n=20，输出结果为：2 3 5 7 11 13 17 19，这些数都是小于等于20的素数。

以下是使用筛选法求解小于 n 的所有素数的 Python 代码： ```python def sieve_of_eratosthenes(n): primes = [True] * (n + 1) primes[0] = primes[1] = False for i in range(2, int(n ** 0.5) + 1): if primes[i]: for j in range(i * i, n + 1, i): primes[j] = False return [i for i in range(2, n + 1) if primes[i]] ``` 该函数使用布尔数组 primes 来表示每个数字是否为素数，首先将所有数字初始化为 True，然后从 2 开始遍历到 n 的平方根，如果当前数字 i 是素数，则将 i 的倍数标记为非素数。最后返回所有标记为素数的数字。