fork(5) 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 5548KB
comments (?)
stdin
copy 
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
100000000000
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 10000000 = 448
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 10000000000 = 2304
Maximum number of divisors of any number less than 100000000000 = 4032
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/rCoxM4
language:
C (gcc 8.3)
created:
2 years 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!