埃式筛法

#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;
}