任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 ，如：n=p1^a1p2^a2…pn^an 如果某个数字是p的倍数，你无法知道这个数字是p^x或者p^y，所以要把p在n范围内的每个倍数都要询问一次，每个素数都要这样询问，这样就可以确定1-n的任意一个数字了。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1010; bool isPrime[MAXN]; void getPrime(int n) { isPrime[0] = isPrime[1] = true; for(int i = 2; i <= n; ++i) { if(!isPrime[i]) { for(int j = i+i; j < MAXN; j += i) isPrime[j] = true; } } } int main() { int n; cin >> n; getPrime(n); int res = 0; for(int i = 1; i <= n; ++i) { if(!isPrime[i]) { int p = i; while(p <= n) { p *= i; ++res; } } } cout << res <<endl; return 0; }