fork(288) download
  1. #include <stdio.h>
  2.  
  3. unsigned long long n, res;
  4. int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};
  5.  
  6. unsigned long long mul(unsigned long long a, unsigned long long b){
  7. unsigned long long res = 0;
  8.  
  9. while (b){
  10. if (b & 1LL) res = (res + a);
  11. if (res >= n) return 0;
  12. a = (a << 1LL);
  13. b >>= 1LL;
  14. }
  15.  
  16. return res;
  17. }
  18.  
  19. void backtrack(int i, int lim, unsigned long long val, unsigned long long r){
  20. if (r > res) res = r;
  21. if (i == p) return;
  22.  
  23. int d;
  24. unsigned long long x = val;
  25.  
  26. for (d = 1; d <= lim; d++){
  27. x = mul(x, primes[i]);
  28. if (x == 0) return;
  29. backtrack(i + 1, d, x, r * (d + 1));
  30. }
  31. }
  32.  
  33. int main(){
  34. /* Tested for n <= 10^18 */
  35.  
  36. p = sizeof(primes) / sizeof(int);
  37.  
  38. while (scanf("%llu", &n) != EOF){
  39. res = 0;
  40. backtrack(0, 100, 1, 1);
  41. printf("Maximum number of divisors of any number less than %llu = %llu\n", n, res);
  42. }
  43. return 0;
  44. }
  45.  
Success #stdin #stdout 0s 2296KB
stdin
10
100
1000000
1000000000
1000000000000
1000000000000000
1000000000000000000
stdout
Maximum number of divisors of any number less than 10 = 4
Maximum number of divisors of any number less than 100 = 12
Maximum number of divisors of any number less than 1000000 = 240
Maximum number of divisors of any number less than 1000000000 = 1344
Maximum number of divisors of any number less than 1000000000000 = 6720
Maximum number of divisors of any number less than 1000000000000000 = 26880
Maximum number of divisors of any number less than 1000000000000000000 = 103680