首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数

热度指数：31374 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 使用下方所描述的筛选法，求解 $n$ 以内的全部素数，同时输出被置为 $0$ 的整数个数。

$\hspace{15pt}$ 筛选法求解的过程为：
${\hspace{20pt}}_\texttt{1.}\,$ 将 $2$ 到 $n$ 之间的整数放在数组内存储；
${\hspace{20pt}}_\texttt{2.}\,$ 将数组中 $2$ 之后的所有能被 $2$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{3.}\,$ 将数组中 $3$ 之后的所有能被 $3$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{4.}\,$ ……；以此类推，直到将数组中 $n$ 之后的所有数都置为 $0$ 为止；
${\hspace{20pt}}_\texttt{5.}\,$ 此时，数组中剩余的非 $0$ 的数即为 $n$ 以内的全部素数。

【名词解释】
$\hspace{15pt}$ 素数：也称质数。一个大于 $1$ 的正整数，如果除了 $1$ 和它自身以外不再有其他因数，那么这个数被称作素数。特殊地， $1$ 既不是素数也不是合数。

输入描述:

在一行上输入一个整数 。

输出描述:

第一行输出若干个整数，表示  以内的全部素数，用空格分隔。
第二行输出一个整数，表示被置为  的整数个数。

示例1

输入

输出

2 3 5 7 11 13 17 19
11

算法知识视频讲解

西西西西西西西

发表于 2021-09-15 13:18:22

#include <stdio.h> int main() { int n = 0; int arr[100] = { 0 }; //多组输入 while (~scanf("%d", &n)) { // 展开全文

牛客171676524号

发表于 2021-10-03 12:04:26

这是一道很好的算法题。。。 1.涉及推导式生成数据列表 2.涉及列表元素的判断、列表元素的删除 3.涉及列表的解包输出、涉及删除元素个数的计算 n = int(input()) # 用推导式求出整个数组的列表 lines = [i for i in range(2,n+1)] # 循环遍历，展开全文