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


اعداد ۱ تا ۱۰ میلیون را در نظر بگیرید. می‌دانیم پر مقسوم‌علیه‌ترین عدد از بین این اعداد، عدد ۸۶۴۸۶۴۰ است که ۴۴۸ است. چهارمین پر مقسوم علیه‌ترین عدد این بازه چند است؟

به عبارت دیگر، اگر اعداد را بر حسب تعداد مقسوم علیه‌هایشان مرتب کنیم و اولین عدد، ۸۶۴۸۶۴۰ باشد، در آن‌ صورت چهارمین عدد چند است؟

اگر آن عدد $D$ باشد؛ باقی‌مانده‌ی تقسیم $D$ بر $\Delta$ چند است؟




<پاسخ>


<code c>‎


#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; 
}



</code>




</پاسخ>
  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]