埃式筛法

做法：做法其实很简单，

首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nloglogn)。

#include <stdio.h>
int fun(int n);

int main() {
	int n;
	scanf("%d", &n);

	int ans = fun(n);
	printf("%d\n", ans);

	return 0;
}

int fun(int n) {
	//all 素数
	//筛除
	int num[n + 1];
	int i;
	int count = 0;
	for (i = 0; i < n; i++) {
		num[i] = 1;
	}
	num[0] = 0;
	num[1] = 0;
	int j;
	for (j = 2; j <= n; j++) {
		if (num[j] == 1) {
			count++;
			int x;
			for (x = 2 * j; x <= n; x = x + j) {
				num[x] = 0;
			}

		}
	}
	return count;
}