对任意整数 a 存在唯一的 a = k1^b1 * k2^b2 * .... * kn^bn 其中 ki为素数,bi为正整数 显然 所有素数都要问一遍 如果对任意 ki^bj <= n 都问一遍 那<=n的任意一个数都能确定 因为 答案就是x = lcm(ki^bj) 其中 x 是 ki^bj 的倍数 所以一共需要问 ∑bi = ∑log(n)/log(ki)
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<queue> #include<sstream> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> const int N = 1e3 + 5; bool isPrimer[N]; void primer(int n){ fill(isPrimer+2,isPrimer+n+1,true); for(int i=2;i<=n;++i){ for(int j = i*i;j<=n;j+=i){ isPrimer[j] = false; } } } int slove(int n){ primer(n); int ans = 0; for(int i = 2;i<=n;++i){ if(isPrimer[i]){ ans += log(n)/log(i); } } return ans; } int main() { //freopen("/home/lu/Documents/r.txt","r",stdin); //freopen("/home/lu/Documents/w.txt","w",stdout); int n; scanf("%d",&n); printf("%d\n",slove(n)); return 0; }