java-beginner.com ブログ

プログラミングを学習するブログ(Javaをメインに)

Project EulerのProblem 1~5をやってみた

投稿日:

最終更新日:2016年10月16日

アイキャッチ

こんにちは。「Javaを復習する初心者」です。

Project Eulerという数学の問題サイトがあります。そのサイトのProblem 1から5を解いてみました。

Problem 1

自分なり直訳してみました。

もし10未満の自然数で3または5の倍数を全て挙げるならば、3, 5, 6そして9である。それら倍数の合計は23である。

1000未満の3または5の倍数すべての合計を求めよ。

上記の数値を求めるため、メソッドを作ってみました。引数n未満の3または5の倍数すべての合計を求めるメソッドです。

ソース

    private int sumBelow(int n) {
        int sum = 0;
        for (int i = 1; i < n; i++) {
            if (i % 3  == 0 || i % 5 == 0) {
                sum += i;
            }
        }
        return sum;
    }

for文のiは0から始めても答えに影響はないですが、余計な処理なのでiは1からにしました。「3または5の倍数」はプログラムでは「3の倍数または5の倍数」と考えれば良く、演算子「||」を使いました。倍数であることは割り算の余りが0であれば良いということです。

Problem 2

自分なり直訳してみました。

Fibonacci数列の各行は前の2項を足すことで生成される。1と2で出発し、最初の10項は次のようになる:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

そのFibonacci数列で4百万を超えない項を考え、偶数値の合計を求めよ。

上記数値を求めるため、メソッドを作ろうかと思ったのやめました。一般項を求めるのと合計を出力するの一緒に処理することにしてmainに直接記述しました。

ソース

        int a;
        int b = 1;
        int term = 2;
        int sum = 2;
        while (term < 4000000) {
            a = b;
            b = term;
            term = a + b;
            if (term % 2 == 0) {
                sum += term;
            }
        }
        System.out.println(sum);

4百万を超えない項というが第何項であるのかは知る必要はないため、繰り返し処理はwhile文を使いました。気を付けるのは、sumの初期値を2にすることです。上記の場合はwhile文の処理は第3項から求めるようになっているからです。「偶数」は2で割ると0という条件になります。

Problem 3

自分なり直訳してみました。

13195の素因数は5, 7, 13そして29である。

数600851475143の最大素因数は何か?

与えられた数が素数かどうかを判定するメソッドを作って、以下のようにプログラムを作りました。

ソース

    private void test() {

        long targetNumber = 600851475143L;
        long factor = 1;
        for (long i = (int)Math.sqrt((double)targetNumber) ; i > 1; i--) {
            if (targetNumber % i == 0 && checkPrimaryOf(i)) {
                factor = i;
                break;
            }
        }
        System.out.println(factor);

    }

    private boolean checkPrimaryOf(long n) {
        for (int i = 2; i <= (int)Math.sqrt((double)n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

最大の素因数を求めるため、まず因数であるかどうかを調べます。つまり、割った余りが0になるかどうかです。もし因数ならばそれが素数かどうかを調べるという考え方をしました。最大の素因数を求めればよいので、for文の開始は600851475143の平方根の整数部分にしました。素因数があるなら、この数以下になるからです。

素数であるかどうかの判定は上記と同様に2から「その数の平方根の整数部分」までに因数を持つかどうかで確認しています。

Problem 4

自分なり直訳してみました。

回文数は両方から同じように読める。2桁の数の積からなる回文数で最大のものは9009 = 91 × 99である。

3桁の2つの数の積からなる回文数で最大のものを求めよ。

以下のようにプログラムを作りました。

ソース

    private void test() {
        int palindromicNumber = 0;
        for (int i = 999; i > 900; i--) {
            for (int j = 999 - (999 - i); j > 900; j--) {
                int n = i * j;
                if (checkPalindromicity(n) && palindromicNumber < n) {
                    palindromicNumber = n;
                }
            }
        }
        System.out.println(palindromicNumber);
    }

    private boolean checkPalindromicity(int n) {
        return Integer.valueOf((new StringBuilder(String.valueOf(n)).reverse().toString())) == n;
    }

for文で地道に調べる方法にしました。掛け算は順不同なので少し工夫しています。i,jを999から900までにしたのですが、数が一つもなければ今度は800台を調べようかなと思って、この範囲にしました。回文の箇所はちょうどStringBuilder#reverseメソッドがあるので、使いました。nを文字列にしてリバースして数値に戻しています。

Problem 5

自分なり直訳してみました。

2520は1から10各々で割り切れる数のうち最小の数である。

1から20のすべてで割れる最小の正の数は何か。

次のようにプログラムを作りました。

ソース

    private void test() {
        int num = 2;
        while (true) {
            if (check(num)) {
                break;
            }
            num ++;
        }
        System.out.println(num);
    }

    private boolean check(int n) {
        for (int i = 2; i <= 20; i++) {
            if (n % i != 0) {
                return false;
            }
        }
        return true;
    }

数字の2から始めて、2から20で割り切れるかどうかを調べているだけです。最初にそのような数が見つかったらそれを出力しています。