چهارمین پرمقسوم علیه‌ترین

‎
 
 
#include <iostream> 
#include <vector> 
using namespace std; 
 
const int N = 10*1000*1000; 
bool p[N]; 
int f[N], a[N]; 
vector<int> primes; 
 
bool fcmp(const int &x, const int &y) 
{ return f[x] > f[y]; } 
 
int main() { 
  for (int i=2; i<=N; i++) 
    if (!p[i]) {  
      for (int j=i; j<=N; j+=i) 
       p[j] = true; 
      primes.push_back(i); 
    } 
 
  for (int i=1; i<=N; i++) { 
    int k = i; 
    int ans = 1; 
    for (int j=0; j<primes.size(); j++) { 
      int y = primes[j]; 
      if (y * y > k) break; 
      int c = 0; 
      for (; k % y == 0; k /= y) 
        c++; 
      ans *= (c+1); 
    } 
 
    if (k > 1) 
      ans *= (1 + 1); 
    f[i] = ans; 
  } 
 
  for (int i=1; i<=N; i++) a[i] = i; 
  sort(a+1, a+N+1, fcmp); 
  cout << a[4] << endl; 
 
  return 0; 
}