高质量题解|埃氏筛选求质数

题目大意

通过埃氏筛法选出 $2$ ~ $n$ 中的质数

考纲知识点

输入输出、分支结构、循环结构、一位数组、算术运算符、数学函数、埃氏筛法、基础数学知识、基础数据类型、变量的定义以及使用

数据范围

$2≤n≤10000000$

解题思路

埃氏筛法:
计算出 $\sqrt{n}$ 的近似值,找到近似值内的质数,删除所有近似值内质数的倍数(从 $2$ 倍开始),剩余的都是质数

定义一个 $\texttt{bool}$ 类型的变量,0表示质数,1表示合数
因为 $1$ 既不是质数也不是合数,所以将 $1$ 定义为 $1$(因为我们要找质数,所以可以将 $1$ 定义为不是质数的那一类)
计算出 $\sqrt{n}$ 的近似值,但是返回值为浮点数类型,所以需要用整数变量 $b$ 将 $\sqrt{n}$ 的近似值强行转换成 $\texttt{int}$ 类型
从 $2$ ~ $\sqrt{n}$ 依次判断当前是否为质数,如果不是则将当前的数定义为1
判断当前数字是否为质数,如果是则输出

参考程序

#include <bits/stdc++.h>
using namespace std;
//1~n的所有素数 n <= 1000
bool a[10000010];//0:素数  1:合数 
int main(){
	int n;
	cin >> n;
	//1.标记下标为 1的位置 
	a[1] = 1;
	//2.计算 n的平方根
	int b = sqrt(n);
	//3.找不到大于根号 n的素数
	for(int i = 2;i <= b;i++){
		//3.1当前是否为素数 
		if(a[i] == 0){
			for(int j = i * 2;j <= n;j += i){
				a[j] = 1;
			}
		}
	} 
	//遍历数组,判断当前是否为 0,输出下标
	for(int i = 1;i <= n;i++){
		if(a[i] == 0){
			cout << i << " ";
		}
	} 
	return 0;
}

时间复杂度

$O(\sqrt{n})$(平方根时间复杂度)
质数判断

空间复杂度

$O(n)$(线性空间复杂度)
定义一个数组用于储存0和1

---

$\color{red}题解仅供学习参考使用$

抄袭、复制题解,以达到刷 AC 率/AC 数量或其他目的的行为,在ACGO是严格禁止的