こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 6から10を解いてみました。
Problem 6
自分なり直訳してみました。
自然数最初の10個の2乗の和は
1^2 + 2^2 + … + 10^2 = 385
自然数最初の10個の和の2乗は
(1 + 2 + … + 10)^2 = 55^2 = 3025
よって、自然数最初の10個の和の2乗と2乗の和の差は3025 − 385 = 2640である。
自然数最初の10個の和の2乗と2乗の和の差を求めよ。
ソース
private void test() {
System.out.println(squareOfSum() - sumOfSquares());
}
private int sumOfSquares() {
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i * i;
}
return sum;
}
private int squareOfSum() {
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i;
}
return sum * sum;
}2乗の和と和の2乗という2種類の数が登場しています。なので、sumOfSquaresメソッドとsquareOfSumメソッドを作りました。それぞれのリターンの差を求めることで問題の回答が得られます。int型の範囲を超えない前提ですが。
Problem 7
自分なり直訳してみました。
素数を最初の6個並べると2, 3, 5, 7, 11, and 13で、6番目の素数は13である。
10001番目の素数を求めよ。
ソース
List<Integer> primeNumbers = new ArrayList<>();
private void test() {
primeNumbers.add(2);
int count = 1;
int num = 3;
while (count != 10001) {
if (check(num)) {
primeNumbers.add(num);
count ++;
}
num ++;
}
System.out.println(primeNumbers.get(primeNumbers.size() - 1));
}
private boolean check(int num) {
for (Integer primeNumber : primeNumbers) {
if (num % primeNumber == 0) {
return false;
}
}
return true;
}素数を格納するArrayListを使ってみました。while文の箇所はArrayList#size()メソッドでも良いのですが、ループごとにsizeメソッドを実行すると遅くなると考えて、int型変数countを使いました。
checkメソッドは引数numが素数かどうかを判定するメソッドです。ArrayListにはnumを超えない素数すべてが格納されるようになっているため、ArrayListに格納されている数で割り切れるかどうかを判定してます。素数の定義は1と自身以外に約数を持たないということですが、倍数の性質を考えると、自身を超えない素数全てで割り切れないなら素数ということになります。
Listに格納した最後の要素が最大の素数です。
Problem 8
自分なり直訳してみました。
1000個の数字における、4つの隣接した数字の積が最大のものは9 × 9 × 8 × 9 = 5832である。
～数字一覧～
13個の隣接した数字の積が最大のものを求めよ。その積の値は何か。
ソース
String digits = "73167176531330624919225119674426574742355349194934"
+ "96983520312774506326239578318016984801869478851843"
+ "85861560789112949495459501737958331952853208805511"
+ "12540698747158523863050715693290963295227443043557"
+ "66896648950445244523161731856403098711121722383113"
+ "62229893423380308135336276614282806444486645238749"
+ "30358907296290491560440772390713810515859307960866"
+ "70172427121883998797908792274921901699720888093776"
+ "65727333001053367881220235421809751254540594752243"
+ "52584907711670556013604839586446706324415722155397"
+ "53697817977846174064955149290862569321978468622482"
+ "83972241375657056057490261407972968652414535100474"
+ "82166370484403199890008895243450658541227588666881"
+ "16427171479924442928230863465674813919123162824586"
+ "17866458359124566529476545682848912883142607690042"
+ "24219022671055626321111109370544217506941658960408"
+ "07198403850962455444362981230987879927244284909188"
+ "84580156166097919133875499200524063689912560717606"
+ "05886116467109405077541002256983155200055935729725"
+ "71636269561882670428252483600823257530420752963450";
private void test() {
int[] numbsrs = new int[digits.length()];
for (int i = 0; i < digits.length(); i++) {
numbsrs[i] = digits.charAt(i) - '0';
}
long max = 0;
for (int i = 0; i < numbsrs.length - 13; i++) {
long p = getProduct(numbsrs, i);
if (max < p) {
max = p;
}
}
System.out.println(max);
}
private long getProduct(int[] numbers, int index) {
long product = 1L;
for (int i = index; i < index + 13; i++) {
product *= numbers[i];
}
return product;
}変数digitsに格納している数字の列が問題文で与えられた数字の列です。隣接13個の積を計算し、最大値を求めるのですが、毎回charAtメソッドを使うと時間がかかりそうなので、最初にint配列に格納しなおしました。charを取り出すので「digits.charAt(i) – ‘0’」というように文字コードの差を取ることで同じ数字をint型配列に格納することができます。
getProductメソッドは隣接13個の積を取得するメソッドです。特に例外処理はしていません。最初int型で計算していたのですが、int型の範囲を超えていたので、回答を間違えました。long型にすることで範囲を超えることなく計算できました。
Problem 9
自分なり直訳してみました。
ピタゴラス数とはa < b < cで a^2 + b^2 = c^2を満たす数の組である。 例えば、3^2 + 4^2 = 9 + 16 = 25 = 5^2である。 a + b + c = 1000となるピタゴラス数が一意的に存在する。 その積abcを求めよ。
ソース
Loop: for (int a = 1; a < 1000; a++) {
for (int b = 1; b < 1000; b++) {
int c = 1000 - a - b;
if (a * a + b * b == c * c) {
System.out.println(a * b * c);
break Loop;
}
}
}aとbをfor文で1から順番に調べる方法を使いました。特に工夫らしいところはないです。for文の2重ループになっているため、break文のためにラベル構文を使ってます。メソッドを別に定義にしてreturnした方が分かりやすいかもしれません。必ず見つかる前提でwhile文にしても良いと思います。
Problem 10
自分なり直訳してみました。
10未満の素数の和は2 + 3 + 5 + 7 = 17である。
2百万を超えない素数の全ての和を求めよ。
ソース
boolean[] numbers = new boolean[2000000];
private void test() {
numbers[2] = true;
for (int i = 3; i < numbers.length; i+=2) {
if (check(i)) {
numbers[i] = true;
}
}
long sum = 2;
for (int i = 3; i < numbers.length; i += 2) {
if (numbers[i]) {
sum += i;
}
}
System.out.println(sum);
}
private boolean check(int num) {
for (int i = 2; i <= (int)Math.sqrt(num); i++) {
if (numbers[i] && num % i == 0) {
return false;
}
}
return true;
}以前に素数の問題が出たときはListを使いましたが、200万までの素数を扱うため、Listはやめました。実際はListを使っていたらすごく時間がかかってしまって、使うのをやめました。その代わりの案として、boolean型配列を用意して、要素番号をそのまま自然数に対応させ、素数ならばtrueを格納するという方法を使いました。boolean型配列の初期値はfalseなので、trueに設定することのみ記述しています。