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..
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)
Thank you for your concern.So what should be the remedy? Use vector.reserve?
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)
With the following snippet there are no reallocations of vectors:
it also MLEs? O(n sqrt(n)) memory
It is also not cache-friendly. Storing multiples is much faster than storing divisors.
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: