题解 | 筛选法求素数

//埃拉托斯特尼筛法(虽然难，但是最高效)

#include<stdio.h>
int main()
{
	int n, arr[101];
	while ((scanf("%d", &n))==1)
	{
		for (int a = 0; a <= n; a++)
		{
			arr[a] = 1;
		}
		arr[0] = arr[1] = 0;
		int count = 0;
		for (int b = 2; b * b <= n; b++)
		{
			if (arr[b] == 1)
			{
				for (int c = b * b; c <= n; c += b)
				{
					if (arr[c] == 1)
					{
						arr[c] = 0;
						count++;
					}
				}
			}
		}
		for (int d = 2; d <= n; d++)
		{
			if (arr[d] == 1)printf("%d ", d);
		}
		printf("\n%d\n", count);
	}
}