Java で与えられた数の約数を見つける
この記事では、Java で特定の数の個別の因数または除数を見つける方法を学習します。
Java で与えられた数の約数を見つける
方法 1: ブルート フォース アプローチ
簡単な方法は、1 から n までのすべての数字をトラバースし、それらが n を適切に分割する (つまり、余りをゼロにする) かどうかを確認することです。 はいの場合、それは要因ではなく、他の要因です。
コード例:
import java.io.*;
class test {
public static void main(String[] args) {
int n = 24;
for (int i = 1; i <= n; i++) {
if (n % i == 0)
System.out.println(i);
}
}
}
出力：
1
2
3
4
6
8
12
24
方法 2: n/2 までトラバースする
最初の方法から、n までトラバースするのではなく、n/2 で停止できることがわかります。これは、n/2 より大きい数値は、数値 n の因数になることは決してないためです。 番号そのもの。
たとえば、数 n は 100 であり、n/2 は 50 であり、51 や 52 のように 50 より大きい数は 100 の因数になることはありません。
コード例:
import java.io.*;
class GFG {
public static void main(String[] args) {
int n = 24;
for (int i = 1; i <= n / 2; i++) {
if (n % i == 0)
System.out.println(i);
}
System.out.println(n);
}
}
上記のコードでは、数値 n 自体が因数であるため、ループの後に追加の print ステートメントを記述しています。
出力：
1
2
3
4
6
8
12
24
方法 3: sqrt(n) までたどる
小さな観察を行うことで、2 番目の方法をさらに最適化できます。 よく見ると、要因がペアで発生していることがわかります。
たとえば、n = 100 で、その因数は 1,2,4,5, 10, 20, 25, 50, 100 です。したがって、ここで可能な異なるペアは (1,100), (2,50), (4,25), (5,20), (10,10).
したがって、最大で、sqrt(n) までの数値をチェックする必要があります。 この場合は 10 です。最後の (10,10) は特殊なケースです。数値が因数であることがわかっているからです。
コード例:
import java.io.*;
class GFG {
public static void main(String[] args) {
int num = 24;
for (int i = 1; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
if (num / i == i)
System.out.println(i);
else {
System.out.println(i);
System.out.println(num / i);
}
}
}
}
}
出力：
1
24
2
12
3
8
4
6
上記の出力では、因子はソートされていません。 auxiliary スペースを使用してソートされた出力を取得できます。
コード例:
import java.io.*;
import java.util.*;
class GFG {
public static void main(String[] args) {
int num = 24;
ArrayList<Integer> store = new ArrayList<>();
for (int i = 1; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
if (num / i == i)
System.out.println(i);
else {
System.out.println(i);
store.add(num / i);
}
}
}
for (int j = store.size() - 1; j >= 0; j--) System.out.println(store.get(j));
}
}
出力：
1
2
3
4
6
8
12
24
上記のコードでは、ArrayList を使用していくつかの要素を保存し、最後に ArrayList の内容を逆の順序で出力しました。
