rebel_roar's blog

By rebel_roar, history, 5 days ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rebel_roar (previous revision, new revision, compare).

»
5 days ago, # |
  Vote: I like it +5 Vote: I do not like it

sqrt may be $$$O(1)$$$ but it has a high constant factor. Computing it once and storing it in a variable lim passes.

»
5 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Indeed, the sqrt function is the culprit: it is a quite slow mathematical function and calculating it many times can easily lead to TLE.

»
5 days ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.