题解 | #筛选法求素数#

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#define NUM 100
int main()
{
	int num = 0;
	while (~scanf("%d", &num))//多组输入
	{
		int arr[NUM] = { 0 };
        //向数组中存入数据
		for (int i = 2; i <= num; i++)
		{
			arr[i] = i;//一一对应上
		}

		//筛选法
		
		for (int i = 2; i <= num; i++)
		{
			for (int j = i + 1; j <= num; j++)//将数组中2之后的所有能被2整除的数清0
				                              //再将3之后的所有能被3整除的数清0 
			{
				if (arr[j] % i == 0)//将不是素数的数赋值为 0
				{
					arr[j] = 0;
				}
			}
		}

		//输出
		int cnt = 0;//计数器  //统计不是素数的数
		for (int i = 2; i <= num; i++)
		{
			if (arr[i] != 0)
			{
				printf("%d ", arr[i]);//输出素数
			}
			else
				cnt++;
		}
		printf("\n%d\n", cnt);//输出不是素数的数
	}



	return 0;
}