Code efficiency example

[atomic totem]

i only started learning about efficiency a while ago, and i'd like to see an example of a code. i want to get a number and print all numbers that have a square root, you can do it easily with an efficiency of O(n), but ive heard you could do it more efficiently, how would i do that?

[toxic bluff]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[atomic totem]

for example, if i would enter 17, i would get "1, 4, 9, 16"

[limber skiff]

Instead of checking each number from 1 to 17 if they have a square root, just keep on generating squares until you overshoot your limit

[atomic totem]

what does that mean

thats still a for loop that goes over the number

if i understood you correctly

[limber skiff]

for (int i=0; i*i < N; i++)
    print(i*i)

[atomic totem]

oh

WOW OKAY

thats a smart idea

[limber skiff]

That way, you only have sqrt(N) loops as oppose to N loops

[atomic totem]

so thats basically o(sqrt(n))

wow okay thats a smart solution

thank you for this example

so is it correct to say this?

@limber skiff

since checking 0 * 0 means basically nothing

[toxic bluff]

@atomic totem Has your question been resolved? If so, run !solved :)

[limber skiff]

Depends if you want 0 as part of ypur answer. If ypu don't, hen starting with 1 is correct

Also big O ignores constant scaling and constant addition.
O(x+1) is equivalent to O(x)

[atomic totem]

oh okay

say i want to make it a bit harder, @limber skiff

a function that checks

ok wait

so basically

void function(int a, int b) // A > B
{
  for(int i = a; i >= b; i--)
  {
    if(i % b == 0)
    {
      printf("%d ",i);
    }
  }
}

something like this

how would i make it efficient?

currently its O(a-b)

[limber skiff]

After finding the first valid i then, i -= b will also be valid

[atomic totem]

hm yeah thats right

how would i implement that though

huh

i saw a message