题目大意
通过埃氏筛法选出 222 ~ nnn 中的质数
考纲知识点
输入输出、分支结构、循环结构、一位数组、算术运算符、数学函数、埃氏筛法、基础数学知识、基础数据类型、变量的定义以及使用
数据范围
2≤n≤100000002≤n≤100000002≤n≤10000000
解题思路
> 埃氏筛法:
> 计算出 n\sqrt{n}n 的近似值,找到近似值内的质数,删除所有近似值内质数的倍数(从 222 倍开始),剩余的都是质数
定义一个 bool\texttt{bool}bool 类型的变量,0表示质数,1表示合数
因为 111 既不是质数也不是合数,所以将 111 定义为 111(因为我们要找质数,所以可以将 111 定义为不是质数的那一类)
计算出 n\sqrt{n}n 的近似值,但是返回值为浮点数类型,所以需要用整数变量 bbb 将 n\sqrt{n}n 的近似值强行转换成 int\texttt{int}int 类型
从 222 ~ n\sqrt{n}n 依次判断当前是否为质数,如果不是则将当前的数定义为1
判断当前数字是否为质数,如果是则输出
参考程序
时间复杂度
O(n)O(\sqrt{n})O(n )(平方根时间复杂度)
质数判断
空间复杂度
O(n)O(n)O(n)(线性空间复杂度)
定义一个数组用于储存0和1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解仅供学习参考使用\COLOR{RED}题解仅供学习参考使用题解仅供学习参考使用
抄袭、复制题解,以达到刷 AC 率/AC 数量或其他目的的行为,在ACGO是严格禁止的
