AcWing 198. 反素数
原题链接
中等
作者:
Abosite
,
2021-07-30 19:20:41
,
所有人可见
,
阅读 283
#include<iostream>
#include<cstdio>
using namespace std;
const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n;
long long ans = 1;
int Max = 0;
void dfs(long long x, int cur, int pre, long long cnt) {
if(cnt > Max) {
Max = cnt;
ans = x;
}
else if(cnt == Max) ans = min(ans, x);
if(cur == 10) return;
for(int i = 1; i <= pre; i++) {
x *= primes[cur];
if(x > n) break;
dfs(x, cur+1, i, cnt*(i+1));
}
}
int main() {
cin >> n;
dfs(1, 0, 30, 1);
cout << ans << endl;
return 0;
}