fork download
copy 
  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 0.01s 5288KB
comments (?)
stdin
copy 
10
100
1000
10000
100000
1000000
100000000
1000000000
1000000000000
1000000000000000
1000000000000000000
stdout
copy 
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 1000 = 32
Maximum number of divisors of any number less than 10000 = 64
Maximum number of divisors of any number less than 100000 = 128
Maximum number of divisors of any number less than 1000000 = 240
Maximum number of divisors of any number less than 100000000 = 768
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
https://ideone.com/hsKpQo
language:
C (gcc 8.3)
created:
1 day 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!