method of factorization- logic

Question

I have seen many writing factorization logic like this
1. starting from i = 2
2. using i*i <= number condition for loop

for(int i = 2; i*i <= number; i++){
 if(number % i == 0)
   // some code
}

My doubt is: what is the need of using i*i<=number. What is he optimizing ?

score 0 · Accepted Answer · edited May 23 '17 at 12:23

0

Factors of a number are paired. For example, the number 30 has factors 1, 2, 3, 5, 6, 10, 15, and 30:

1  2  3  5
|  |  |  |
30 15 10 6

So you don't need to calculate all factors, just the first half of them, and get the other half by a simple operation of division.

edited May 23 '17 at 12:23

Community

answered May 11 '16 at 06:43

Yu Hao

+1 SO, we can eliminate all other divisors (factor pairs) by only using upto sqrt(number). In some cases the n remains as a prime number. Ex 58. We iterate only upto 7, by now number is 29, loop exits. If number remains still greater than 1 (as 29>1 here) after loop exits. We should take care of that number, that MUST BE A PRIME. – Sparrow May 11 '16 at 07:03

1 Answers1