fork download
copy 
  1. #include <stdio.h>
  2.  
  3. unsigned long long n, rv, 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) rv = val, 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 * (2 * 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 (%llu)\n", n, res, rv);
  42.     }
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
10
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
100000000000
1000000000000
1000000000000000
1000000000000000000
stdout
copy 
Maximum number of divisors of any number less than 10 = 9 (6)
Maximum number of divisors of any number less than 1000 = 189 (840)
Maximum number of divisors of any number less than 10000 = 567 (9240)
Maximum number of divisors of any number less than 100000 = 1323 (83160)
Maximum number of divisors of any number less than 1000000 = 3645 (720720)
Maximum number of divisors of any number less than 10000000 = 8505 (6126120)
Maximum number of divisors of any number less than 100000000 = 19845 (91891800)
Maximum number of divisors of any number less than 1000000000 = 47385 (931170240)
Maximum number of divisors of any number less than 10000000000 = 107163 (8031343320)
Maximum number of divisors of any number less than 100000000000 = 229635 (77636318760)
Maximum number of divisors of any number less than 1000000000000 = 505197 (931635825120)
Maximum number of divisors of any number less than 1000000000000000 = 4428675 (890488576177200)
Maximum number of divisors of any number less than 1000000000000000000 = 33480783 (941958815880242160)
https://ideone.com/vwWHAs
language:
C (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!