题目

解答：

#include<stdio.h>

#include<string.h>

#define MAXN 5000005

int is_prime[MAXN]; // 用来标记质数
int factor_count[MAXN]; // 用来计数每个数字的质因数数量

void sieve() {
memset(is_prime, 1, sizeof(is_prime));
memset(factor_count, 0, sizeof(factor_count));
is_prime[0] = is_prime[1] = 0; // 0和1既不是奇数也不是偶数
for (int i = 2; i < MAXN; i++) {
if (is_prime[i]) {
for (int j = i; j < MAXN; j += i) {
is_prime[j] = 0; // 标记非质数
factor_count[j]++; // 增加质因数计数
}
}
}
}

int main() {
int n;
scanf(“%d”, &n);
sieve();
int even_count = 0;
for (int i = 2; i <= n; i++) { if (factor_count[i] > 1) {
even_count++;
}
}
printf(“%d\n”, even_count);
return 0;
}