for内部ループをより効率的にするには？

Question

私はJavaの初心者です。私にはこの1つの疑問があります。このコードで内部ループをより効率的にする方法は？

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まで取得しようとしていましたが、内部ループをより効率的にするにはどうすればよいですか？

Answer 1

それはここ関与少し数論だが、あなたがこれを行う場合100がはるかに大きな何かを交換した場合、それは特別に効率的である：あなたがのすべての除数aのためという事実を使用することができます

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(); 
} 

Answer 2

i のような数字bがあります。

すべての除数を見つけて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)の操作を必要とするこの方法では。

Answer 3

このコード時間の複雑さは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