RaFiN_

highest number of divisors

Oct 26th, 2020
852
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //highest number of divisors
  2. #include <stdio.h>
  3.  
  4. unsigned long long n, res;
  5. int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};
  6.  
  7. unsigned long long mul(unsigned long long a, unsigned long long b){
  8.     unsigned long long res = 0;
  9.  
  10.     while (b){
  11.         if (b & 1LL) res = (res + a);
  12.         if (res >= n) return 0;
  13.         a = (a << 1LL);
  14.         b >>= 1LL;
  15.     }
  16.  
  17.     return res;
  18. }
  19.  
  20. void backtrack(int i, int lim, unsigned long long val, unsigned long long r){
  21.     if (r > res) res = r;
  22.     if (i == p) return;
  23.  
  24.     int d;
  25.     unsigned long long x = val;
  26.  
  27.     for (d = 1; d <= lim; d++){
  28.         x = mul(x, primes[i]);
  29.         if (x == 0) return;
  30.         backtrack(i + 1, d, x, r * (d + 1));
  31.     }
  32. }
  33.  
  34. int main(){
  35.     /* Tested for n <= 10^18 */
  36.  
  37.     p = sizeof(primes) / sizeof(int);
  38.  
  39.     while (scanf("%llu", &n) != EOF){
  40.         res = 0;
  41.         backtrack(0, 100, 1, 1);
  42.         printf("Maximum number of divisors of any number less than %llu = %llu\n", n, res);
  43.     }
  44.     return 0;
  45. }
  46.  
RAW Paste Data