【C语言】牛客网BC127 筛选法求素数

描述

用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。

输入描述：
多组输入，每行输入一个正整数（不大于100）。
输出描述：
针对每行输入的整数n，输出两行，第一行，输出n之内（包括n）的素数，用空格分隔，

第二行，输出数组中2之后被清0 的个数。每行输出后换行。

示例1

输入：
20
输出：
2 3 5 7 11 13 17 19
11

思路
1.先将2-n 之间的所有数存放在一个数组
2遍历数组 创建除数变量j 每次遍历将除数j加一，如果被整除就把该元素变为0
3输出 遍历数组 将非0元素输出 定义计数器cnt储存0的数量
AC代码为

#include<stdio.h>
int main()
{
	int n = 0;
	int i = 0;
	scanf("%d", &n);
	int arr[105] = { 0 };
	for (i = 2; i <= n; i++)//储存2--n的整数
	{
		arr[i] = i;
	}
	for (i = 2; i < n; i++)//遍历数组
	{
		int j = 0;
		for (j = i+1; j <= n; j++)//j从i+1开始
		{
			if (arr[j] % i == 0)//如果被整除 就将该元素化为0
			{
				arr[j] = 0;
			}
		}
	}
	int cnt = 0;
	for (i = 2; i <= n; i++)
	{
		if (arr[i] != 0)//如果非0，打印
			printf("%d ", arr[i]);
		else//如果为0 计数器cnt+1
			cnt++;
	}
	printf("\n%d", cnt);
	return 0;
}