Complexity

Hi, I started learning C recently and I don't have much experience. I need to make a program that will factorize an entered integer number and I should also explain the program. No problems with that :). However I should also write the complexity of the program (you know like O(n), O(log2n) etc.). I'm stuck there, how should I write the complexity using n (the entered number)? Basicaly it doesn't depend on how big is the entered number, but how big are his factors. Some big number like 3^20 will be factorized faster than some relatively little prime number like 5413. Can I somehow express my program's compexity using n or there is another way I should do that? Any help will be appreciated.

P.S. yes the program probably can be improved, but that isn't important at the moment (4294967291 is the largest prime that can be stored in unsigned int ...and the program factorizes it for <1s, so I don't think there is any need for faster algorithm :P). Maybe if I used unsigned long long...

P.P.S. sorry, names and text in the program aren't in English, I'm in a hurry, can't translate right now. But you get the point ...I hope ;). Sorry for reading all this :)

I would suppose basically it is something like O(n) - with a high chance of earlying out.

If you need to factorize a lot of numbers you might keep an array of primes at hand :) (Which I think I have used for some Project Euler problems.)

For factorizing just one number I guess it is fast enough.

Code:

---

          fakt[faktBr].osnova=2;
          fakt[faktBr].stepen=0;
          while(n%2==0){
                n/=2;
                fakt[faktBr].stepen++;
          }
          faktBr++;

---

could be made into a function - it is after all repeated twice in your code, and it's complex enough that the overhead of a function call will probably make minimal difference.

Code:

---

    for(i=3;i<=sqrt(n);i+=2){

---

Are you sure that you can not get more than 9 factors by using a value below 2^32? I'm not sure, that's why I'm asking.

--
Mats

I think this means that no factor can be larger than square root of the current value.

Perhaps as an optimization the sqrt call could be moved elsewhere. E.g if a number is not divisible by 3, 5, 7, etc there's no point in recalculating the square root.

Quote:

---

Originally Posted by anon

I think this means that no factor can be larger than square root of the current value.

Perhaps as an optimization the sqrt call could be moved elsewhere. E.g if a number is not divisible by 3, 5, 7, etc there's no point in recalculating the square root.

---

Sorry, I messed up my post - yes, that was what I was meaning to say, but then I changed my mind but didn't remove the code-segment I meant to write the comment on, but after more thinking, I think it is correct to say:
* take the sqrt of n before the loop.
* when you find a factor, after the while loop, re-calculate the sqrt(n) variable [as n is now i ^ stepen smaller].

--
Mats

Quote:

---

Originally Posted by matsp

Are you sure that you can not get more than 9 factors by using a value below 2^32? I'm not sure, that's why I'm asking.

---

Well yes I am :). The smallest number with 10 different factors would be 6692786100 (it's factors are the first 10 primes) and that's over 2^32

Thanks for the other advices too, will try to do it...

P.S. so it's O(n)? Would you mind explaining how you get that? I hope I'm not bothering you too much :).

I tried a little but... If the input is a prime number then I guess the for loop will repeat (sqrt(n)-1)/2 times, right? But then if it's a composite that doesn't apply. How can I put all cases in one formula ...or should I just look at the worst case?

Quote:

---

Originally Posted by mMarko

The smallest number with 10 different factors would be the 6692786100 (it's factors are the first 10 primes) and that's over 2^32

---

Actually, the smallest natural number with 10 different natural number factors is 10!, but then you actually mean prime factors :)

Consequently, your reasoning is correct, though I note that the number is actually 6469693230.

Quote:

---

Originally Posted by laserlight

Actually, the smallest natural number with 10 different natural number factors is 10!, but then you actually mean prime factors :)

Consequently, your reasoning is correct, though I note that the number is actually 6469693230.

---

Well yes we are talking about prime factors, and yes you are right, it's 6469693230, I don't know the number, I calculated it ;) ...don't know if it's my or calculator's fault ...probably mine ;). Anyway I got the correct number the first time, I guess.