Complexity of finding factors of all the numbers from 1 to n

Правка en4, от The_mysterio, 2020-12-03 12:21:07

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..

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский The_mysterio 2020-12-03 12:21:07 26
en3 Английский The_mysterio 2020-12-03 12:20:27 18
en2 Английский The_mysterio 2020-12-03 12:19:32 3
en1 Английский The_mysterio 2020-12-03 12:18:50 1098 Initial revision (published)