public class EuclidsAlgorithm {
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static void main(String[] args) {
int a = 24;
int b = 16;
int gcdResult = gcd(a, b);
System.out.println("GCD of " + a + " and " + b + " is " + gcdResult);
}
}
※19行目でfor文の継続条件式が「 i * i < digits.length 」となっているのは、p * p より小さい倍数は既に他の素数の倍数としてふるい落とされているためです。例えば30までの素数であれば、7*7＝49で30を超えます。5より大きい素数の倍数は既にふるい落とされているので処理は不要なのです。
＜エラトステネスの篩を自分の手で検証する＞
エラトステネスの篩を自分の手で検証する
＜サンプルプログラム＞
import java.util.Scanner;
public class SieveOfEratosthenes {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("いくつまでの素数を知りたいですか？: ");
int n = sc.nextInt();
sc.close();
boolean[] digits = new boolean[n + 1];//配列は0始まり
for (int i = 0; i < digits.length; i++) {
digits[i] = true;//配列はfalseで初期化されているため全てtrue(素数である)にする
}
digits[0] = digits[1] = false;//0と1は素数ではない
for (int i = 2; i * i < digits.length; i++) {
if (digits[i]) {
for (int j = i * i; j < digits.length; j += i) {
digits[j] = false;
}
}
}
for (int i = 2; i < digits.length; i++) {
if (digits[i]) {
System.out.print(i + " ");
}
}
}
}
山崎講師
