http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1536
首先，要知道值为n的答案，则可以这么去想，知道值为n - 1的答案，然后判断下，前面的数字能不能唯一确定n
然后，如果一个数是单独一个质数的k次方，这样是不能唯一确定的。
因为，比如要确定343 = 7 * 7 * 7
根据前面的数字，能被7整除，又能被49整除，不是能唯一确定吗？但是49本身也符合。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> bool is(int val) { int has = 0; for (int i = 2; i <= val; ++i) { if (val % i == 0) { val /= i; has++; while (val % i == 0) val /= i; if (has == 2) return false; } } return true; } void work() { int n; cin >> n; int ans = 0; for (int i = 2; i <= n; ++i) { ans += is(i); } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }