I’m solving this problem ([NUMFACT Problem - CodeChef] from medium section and my solution took 0.67 sec and i got AC , but when i see others code they just took a prime array of size 1009 and got AC in 0.00 sec. Can anyone explain it to me , like if reducing the prime size will decrease so much time then why it gives WA on creating prime of size 100.
In the question it is given that a[i]<=10^6 , so the largest prime factor of the number will be less than sqrt(a[i]) i.e. sqrt(10^6) = 10^3 .
1009 is just a number larger than 1000 , you could take 1001 and it won’t change the result .
If prime size is reduced to 100 then it will only be able to handle number <=100*100. i.e will only pass second test case
1 Like