Блог

Я новичок в Java, и есть один вопрос, который заставляет меня задуматься. Как сделать внутренний цикл for более эффективным в этом коде?

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

Я просто пытался получить множители чисел от 2 до 100, но как я могу сделать внутренний цикл более эффективным?

Здесь немного задействована теория чисел, но если вы сделаете это, это будет особенно эффективно, когда 100 заменяется чем-то гораздо большим:

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

Вы могли бы использовать тот факт, что для каждого делителя a i существует такое число b , что a * b = i .

Найдите все делители a <= sqrt(i) , сохраните b = i/a и распечатайте эти значения позже.

 final int num = 100;
int[] divisors = new int[(int) Math.sqrt(num)];
for (int i = 2; i <= num; i  ) {
    System.out.print("Factors of "   i   " is: ");
    int j = 2;
    int index = 0;
    for (; j * j < i; j  ) {
        if (i % j == 0) {
            System.out.print(j   " ");
            divisors[index  ] = i / j;
        }
    }
    if (j * j == i) {
        // print sqrt(i) only once, if it's integral
        System.out.print(j   " ");
    }
    while (--index >= 0) {
        System.out.print(divisors[index]   " ");
    }
    System.out.println();
}
  

Таким образом, вашему внутреннему циклу нужны только O(sqrt(i)) O(i) операции вместо.

Эта временная сложность кода O(N2) .

  public static void main(String[] args) {

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

  }
  

Попробуйте это, так как вывод вашего кода будет отображаться следующим образом (в порядке возрастания)

 Factors of 24 is: 2 3 4 6 8 12 
  

обратите внимание, но данный код будет отображаться следующим образом (в порядке убывания)

 Factors of 24 is: 12 8 6 4 3 2