The_mysterio's blog

Complexity of finding factors of all the numbers from 1 to n
By The_mysterio, history, 4 years ago, In English

Hello all, I am trying to find the complexity of the below code

"#include <bits/stdc++.h>

using namespace std;

int main() {

long long int n;

cin>>n;

vector<int>factors[1000001];

for(int i=2;i<=n;i++)

{

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

    {

        factors[j*i].push_back(i);

    }

}






return 0;

}"

What I am mainly doing in the code is trying to store factors of all the numbers from 1 to n (n<=1000000). As you can see , factors is a vector of vectors. factors[i] will store all the factors for number i. The code works as follows 1. Fix a number i in the outer loop 2. For all the multiples of i that lies within n, push i as it's factor-->this is being done in the inner loop. According to my calculation, the complexity should be nlog(n) which should easily pass in a time limit of 1s but when I am running the above code on Codechef compiler with n=1000000, the execution time is coming >2s.

If anyone can kindly help, I will be highly obliged. Thank you..

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

it could be because vector push_back is too slow, especially since the size of the each vector is not very large (average size is about 14 factors)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your concern.So what should be the remedy? Use vector.reserve?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i suppose that it would speed it up, not sure which number is most optimal i tested 15 and 30, both of them gave ~850ms on cf (while without reserve gave ~1000ms)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        With the following snippet there are no reallocations of vectors:

            for (size_t i = 2; i <= n; ++i)
        factors[i].reserve(sqrt(i)+5);
        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          it also MLEs? O(n sqrt(n)) memory

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is also not cache-friendly. Storing multiples is much faster than storing divisors.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

AFAIU, if x is a divisor of n then all divisors of x are also divisors of n. So it is not needed to duplicate work as well as to store divisors multiple times, is it?

Maybe this code could help:

Spoiler
→ Reply