### rebel_roar's blog

By rebel_roar, history, 4 days ago,

Can anyone help me, which is more efficient while using in the for loop?

for(u = 2; u <= sqrt(n); u++)

or

for(u = 2; u*u <= n; u++)

Here are my both submission

Using first method — 119098252

Using second method — 119098208

While using the first method i got TLE but the same code using with the second method got Accepted..

I am assuming that method one is calculating sqrt(n) again and again and other one is calculating u*u again and again then why one is got accepted other one is not.

Please tell me the reason behind this?

• +10

 » 4 days ago, # |   0 Auto comment: topic has been updated by rebel_roar (previous revision, new revision, compare).
 » 4 days ago, # |   +5 sqrt may be $O(1)$ but it has a high constant factor. Computing it once and storing it in a variable lim passes.
 » 4 days ago, # |   +8 Indeed, the sqrt function is the culprit: it is a quite slow mathematical function and calculating it many times can easily lead to TLE.
•  » » 4 days ago, # ^ |   0 Thanks
 » 4 days ago, # | ← Rev. 2 →   +3 Usually try not to use sqrt function unless your u*u is larger than LLONG_MAX(if you use long long int)/INT_MAX(if you use int)....
 » 4 days ago, # |   0 And use for(int i = 0; i <= x / i ; i ++) will got $\text{TLE}$But use for(long long i = 0; i * i <= x; i ++) will got $\text{TLE}$ , too.