CODEWITHSUNDEEP
algorithmperformancetime
yobro97
yobro97

Reputation: 1145

Fastest way to find out a number with most divisors

Given a number n how fast can one find the smallest number with most factors and is less than n?
PS:other than the naive approach of finding number of divisors for all numbers upto n.

UPDATE : My observation:

int solve(int primes[],int s,int n)
{
    int i=0;
    while(s<n)
    {
        s*=primes[i];
        i++;
    }
    if(s>n)
        s/=primes[i-1];
    return s;
}
int main()
{
    int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37};
    int n;
    scanf("%d",&n);
    int s=1;
    while(s*2<n)//checking the possibility of existence of any prime such that s*p<n
    {
        s=solve(primes,s,n);
    }
    printf("%d\n",s);
}

The output for this for 100000 is 60060. Is this observation true? Because I don't have any concrete proof of this approach. What I observed is that suppose take a prime array {2,3,5,7,11} and suppose that the given n is 100. Then observe that keep multiplying distinct primes until that point that you get it >100. That is 2*3*5.Repeat multiplying primes from the array from the first element again.That is 2*3*5*2. This is the number required 60 with 12 factors.Now there is no prime that can be multiplied without exceeding 100. Is this observation true? If its true then with primes upto 37 we can deal with n<=10000000 easily.All the numbers below 100 with most factors are 60, 72, 84, 90 and 96. We get the smallest of these numbers with this approach. All have 12 factors. No number below 100 has more than 12 factors.

Upvotes: 1

Views: 2516

Answers (2)

shole
shole

Reputation: 4084

I think this problem can be solved by algorithm similar to Hamming Number, indeed your original concept is very similar to Hamming Number as well.

Hamming Number is a problem to generate number x, where x = 2^i * 3*j * 5*k, from small to large in O(N) where N is the number of hamming number to be generated.

Here, I think similar concept can be used but we have to use the set of prime which is below your upper bound instead of {2,3,5}, we just need to also count the maximum # of prime factors when generating the number, and output it after the number generated is larger than N.

For example, here is the list of hamming number(using {2,3,5} for demo purpose) < 100:

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100

60 = 2^2 * 3^1 * 5^1, total factors = 3*2*2 = 12 or

96 = 2^5 * 3^1, total factors = 6*2 = 12

So there may be multiple answer but you should be able to capture them while generating hamming number.

One can show that it is logically correct because

  1. The numbers are generated by prime numbers (prime factors)
  2. The numbers are generated in order

Note that in your case, basically you are generating all positive numbers from 1 to your upper bound.

Here is a site with tons of example in different language implementing this algorithm to generate hamming numbers: https://rosettacode.org/wiki/Hamming_numbers

Upvotes: 1

Nazarii Bardiuk
Nazarii Bardiuk

Reputation: 4342

Adapting Sieve of Eratosthenes it is doable in O(n^2) time.

  • Start with an array of size n i.e divisors.
  • For each number k less than n increment divisors[k] and all other indexes that are k*i < n
  • Find index of the larger value in divisors

Upvotes: 0

Related Questions