CODEWITHSUNDEEP
c++time-complexityfactors
BlackBeard
BlackBeard

Reputation: 31

Most efficient way to find the common divisors of two numbers upto 10^6

I wanted to store all the divisors of all the numbers from 1 to 10^6. But this seems too slow. This is the preprocess() function of my code:

for(int i=1; i<=1000000; i++)
{
    for(int j=1; j<=i/2; j++)
    {
        if(i%j==0)
            divi[i][j] = true;
    }
}

I used map container like this:

map <int, bool> divi[1000010];

Then I tried to find the common divisors of two given numbers.

preprocess();

int T, A, B;

cin >> T;

while(T--)
{
    cin >> A >> B;

    int common = 0;
    for(it = divi[A].begin(); it!=divi[A].end(); it++)
    {
        if(divi[B][it->first]==true)
            common++;
    }

    cout << common << endl;

How should i approach now to make it faster enough?

Upvotes: 0

Views: 550

Answers (2)

Hans Olsson
Hans Olsson

Reputation: 12507

It depends on what you want: if you only want the common divisors for some specific numbers then the Euclidian algorithm is the solution.

If you really want a list of all divisors for all number 1..n, one solution would be (similar to a Sieve):

  for(int I=1;I<=sqrt(n);++I) {
     for(int j=I;j*I<=n;++j) divi[I*j][j]=divi[I*j][I]=true;
  }

The code complexity of the original one is O(N^2) with first answer it is O(N^1.5). I believe the new formula is O(N*log N)

Upvotes: 1

Bathsheba
Bathsheba

Reputation: 234685

Aside from the fact that using a std::map will be in itself expensive (can't you use arrays?), a quick numerical win is to only go up to the square root of the number in the inner loop.

for (int j = 1; j * j <= i; j++)

(Noting that squaring j is cheaper than the computing the square root of i, and keeps you away from floating point computations.)

This must be coupled with noting that if j is a divisor, then i / j is also a divisor. So you also need to replace

divi[i][j] = true;

with

divi[i][j] = divi[i][i / j] = true;

This optimisation is centred around the computation of the divisors of a single number. There are faster approaches for acquiring the divisors for a set of numbers, but my approach might be sufficient. Downvote if not.

Upvotes: 4

Related Questions