Как усовершенствовать алгоритм поиска множителей числа?

Question

[Денис Каракчиев]

Собственно, простейшая задачка из книжки - усовершенствовать алгоритм поиска всех чисел j, на которые делится всякое число i без остатка, кроме самого себя.

public class Main {
  public static void main(String[] args) {

              for(int i=2; i <= 100; i++) {
                  System.out.print("Factors of " + i + ": ");
                  for (int j = 2; j < i; j++)
                      if ((i % j) == 0) {
                          System.out.print(j + " ");
                         // if (j == i/2) break;
                      }
                  System.out.println();
              }
  }
}

Собственно, нужно уменьшить количество итераций во вложенном цикле. Мое решение в виде задокументированной строчки кода вроде как работает. Вопрос вот в чем: решение кажется слишком наивным, потому как привелось оно 'прямой долбежкой'. Т.е. я посмотрел на результат кода, увидел, что значение числа, на которые i делится без остатка никогда не получается больше, чем 1\2 от i и дописал такую строчку.

Так вот, нет ли менее наивного способа, либо совершенно другого, чего стоило бы заметить?

Answer 1

[tsarevfs]

улучшение 1, чтобы не писать лишнюю проверку в цикле for (int j = 2; j < i/2; j++)
Доказать что это правильно очень легко. Предположим, что нашелся делитель > j / 2. Разделим и получим результат < 2. Не забывайте, что формально число делится само на себя.
Если бы вас интересовала простота числа, а не список всех его делителей достаточно было бы проверять до корня из j. Что тоже легко доказать от противного.

Comments

[Денис Каракчиев]

т.е. мое решение верное, остается только занести его в условие for?
А на счет простых чисел проходили, тоже пришлось вопрос задать, но там с пониманием были проблемы)

[tsarevfs]

Денис Каракчиев: Да, похоже на правду.