【Java】素数判定・カウント_Ver1

今回は入力された数値以下に素数がいくつあるかという問題です。

コード更新しています。解説等はこのままこの記事で解説していますので、解説等読んだ後はVer2のコードを参照してください。

dadainu.hateblo.jp

素数は約数が1と自分自身だけという数値です。例として、2,3,5,7,11...です。処理の流れとして主に二つあります。一つ目は、偶数は2の倍数なので偶数は処理から除きます。二つ目は、入力された数値の平方根より大きい数は必ず平方根以下の素数の公倍数となっているので、平方根以下の数のみを調べます。

上記を元に以下コードです。

import static java.lang.Integer.parseInt;
import static java.lang.System.out;
import java.io.File;
import java.util.Scanner;

public class PrimeNumber {

    public static int maxSize = 1000000;

    public static boolean[] prime = new boolean[maxSize];

    public static void main(String[] args) {
        new PrimeNumber().count();
    }

    public void count() {
        try (Scanner scan = new Scanner(System.in)) {
            countPrime(scan);
        } catch (Exception e) {
            System.exit(0);
        }
    }

    public void count(String inputDataPath) {
        try (Scanner scan = new Scanner(new File(inputDataPath))) {
            countPrime(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void countPrime(Scanner scan) {
        setPrime();
        String inData = "";
        while ((inData = scan.nextLine()) != null && !"".equals(inData)) {
            out.println(primeCount(parseInt(inData)));
        }
    }

    private void setPrime() {
        prime[2] = true;
        for (int i = 3; i < maxSize; i++) {
            if (i % 2 == 0) {
                continue;
            }
            setOddPrime(i);
        }
    }

    private void setOddPrime(int i) {
        boolean isPrime = true;
        for (int j = 1; j <= Math.sqrt(i); j++) {
            if (prime[j] && i % j == 0) {
                isPrime = false;
                break;
            }
        }
        prime[i] = (isPrime) ? true : false;
    }

    private int primeCount(int inData) {
        int count = 0;
        for (int i = 2; i <= inData; i++) {
            if (i != 2 && i % 2 == 0) {
                continue;
            }
            count = (prime[i]) ? ++count : count;
        }
        return count;
    }
}

999999までの数値で素数かどうかの判定リストを作成してから、入力された数値に何個素数があるかを判定リストを元に数えています。この問題は小さい数であればループで解くことのできる問題ですが、大きい数になってくると処理時間が膨大にかかります。どれだけ処理内容を短くするかを考える必要がありますので、今までの問題より頭を使う問題でした。

テストドライバは以下になります。

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import volume0.BaseTest;

public class PrimeNumberTest extends BaseTest {

    private PrimeNumber pn;

    @Before
    public void setUp() throws Exception {
        super.setUp();
        pn = new PrimeNumber();
    }

    @After
    public void tearDown() throws Exception {
        super.tearDown();
    }

    @Test
    public void test() {
        try {
            pn.count("./data/volume0_0009/in.txt");
            outList = outContent.toString().split("\n");
            assertOut(outList, "./data/volume0_0009/out.txt");
        } catch (Exception e) {
            e.printStackTrace();
            printErr(e);
        }
    }
}

テストドライバ内で使用している「in.txt」・「out.txt」は以下になります。

in.txt
10
3
11

out.txt
4
2
5

今回の問題は以下にあります。

素数 | Aizu Online Judge

アルゴリスムで困った時は、以下の本を参考にしてます。Javaに置き換えるのが少々難解ですが、、、

テストドライバで継承しているクラスは以下の記事に記載しています。参考にしてみてください。

dadainu.hateblo.jp