метод factorization- логики

Question

Я видел много написания факторизационных логик как этот
1. начиная с = 2
2. С помощью я * я < = числа условия цикла

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

Я сомневаюсь, что: что нужно использовать i * i < = номер. Что он оптимизирует?

Answer 1

Факторы числа спарены. Например, число 30 имеет факторы 1, 2, 3, 5, 6, 10, 15 и 30:

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

Так что вам не нужно, чтобы рассчитать все факторы, только первая половина из них, и получить вторую половину простой операцией деления.

Связанный вопрос: Efficiently getting all divisors of a given number.