0

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?

Jarod42
  • 203,559
  • 14
  • 181
  • 302
BlackBeard
  • 31
  • 4
  • 2
    Look at [Euclidean_algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) – Jarod42 Nov 02 '16 at 08:45
  • Note that `divi[B][it->first] == true` will create a new map entry if one didn't exist. This gets very costly, particularly for the primes. – molbdnilo Nov 02 '16 at 08:47
  • BTW, `std::map ` might be replaced by `std::set`. – Jarod42 Nov 02 '16 at 08:52
  • 1
    By using sieve method, you might get rid of modulo and division in your preprocessor method. – Jarod42 Nov 02 '16 at 08:54
  • The main saving of a sieve method is that you don't examine all elements, module and division are almost as fast as multiplication. – Hans Olsson Nov 02 '16 at 08:57
  • @Jarod42 Euclidian method will give you the gcd. If you need *all the common divisors* you need: 1. factor the gcd 2. multiply all the (2^n-1) combinations of the gcd factors, multiplicity included. – Adrian Colomitchi Nov 02 '16 at 09:35
  • There's some useful info in a related question: http://stackoverflow.com/questions/35469430/what-is-an-efficient-algorithm-to-find-all-the-factors-of-an-integer/35470770#35470770 . – user3528438 Nov 02 '16 at 09:55

2 Answers2

4

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.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
1

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)

Hans Olsson
  • 11,123
  • 15
  • 38