题解 | #筛选法求素数#

#include<stdio.h>
//筛选法 求 n 以内的素数
#define NUM 1000
int main()
{
	int n = 0;
	//多组输入
	while (~scanf("%d", &n))//~EOF = 0//为假
	{
		int arr[NUM] = { 0 };
		//将 2 ~ n 之间的正整数 存入数组中
		for (int i = 2; i <= n; i++)
		{
			arr[i] = i;//对应 存储
		}

		//筛选法
		for (int i = 2; i <= n; i++)
		{
			for (int j = 2; j <= n; j++)//不断遍历数组中的元素
			{
				if (i == j)//碰到 自身除以自身 就跳过(素数 是只能被 1 和 它自身 整除的数）
				{
					continue;
				}
				if (arr[j] % i == 0)
				{
					arr[j] = 0;//将 不是 素数的数 赋值为 0
				}
			}
		}
		//输出
		int cnt = 0;//计数器  //统计 数组中被 清零的元素的个数，即 不是素数的数
		for (int i = 2; i <= n; i++)
		{
			if (arr[i] == 0)
			{
				cnt++;
				continue;
			}
			if (i == 2)
			{
				printf("%d ", 2);
			}
			else
			{
				printf("%d ", arr[i]);
			}
		}
		printf("\n%d\n", cnt);
		
	}

	return 0;
}