why is the pre-computation time ignored
NloglogN > logN then how can we ignore it.
Prime factorisation using sieve method?
@mehulbhandari358, we are not ignoring it we are just thinking in different context ,
precomputation time is :- O(n log log n)
and time complexity for every query is o(logN)
This method is used in case you have multiple queries say in range >10^5 , In that case using trivial method is not suitable as in that case you have to calculate prime factors from the scratch and cost you some time , but if you use this method then you need precomputation only once and for every query you can find factors in logn
but in the vedio sir said the time complexity is logN ??how is it possible
while passing a vector to function is it necessary to insert " &" in the definition
ex- vector fact(vector & primes) {
…
return factors;
}
and how can we assign an array to vector as sir has done in the code.
vector primes=primesieve(p,10000);
here, primesieve is an array .
@mehulbhandari358, logn is the time complexity for one query, refer this :- https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
yes you have to use ‘&’ this denotes that you are passing argument by reference , similar to passing by pointer, if you pass by value then the argument will make a copy that will cost you o(n) time , here by reference we are using the original primes vector so changes made inside on primes inside the function will persist throughout
vector primes = primesieve(p,10000);
here primesieve returns vector which is the seive , so we are passing the value in the primes variable of type vector , the function is defined earlier, as the vedio is taught assuming you have watched the vedio of seive of erastothenis first
but prime sieve is a void function
can we pass the vector by value ?
yes you can pass vector by value in a function since vector is a data type
primeSieve is not a void function , check at time stamp @3.36 minutes
the return type is vector
can here i do the same ? pass vector by value
@mehulbhandari358, as i mentioned earlier passing by value make a local copy for the function to work on, and making a copy of your vector will cost you o(n) time , instead pass by reference
pls explan how will it cost o(n) time . i will return the address by passing the value , as we do in the case of other datatypes.
if you make a copy of vector then it will take o(n) time (n is the number of element in original vector) as first it will alocate n size memory to the vector and then run a for loop to add elements from the original vector , this is already defined in the constructor of vector stl .
refer this for an example on how passing by reference and passing by value make a difference, also,
i don’t understand what you mean by return the address by passing the value,
I have sent you my mobile number , you can call in case you have trouble understanding through text
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.