素数について

お久しぶりとなってしまいました。

今回もAtCoderの記事です。

Web開発のほうはもう少しで記事として書けるくらいの内容までいくので、しばしお待ちください。

ちなみに、前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

素数とは

素数とは、1とその数字以外で割り切れない数です。（1は素数ではない）

よく某大学がネタにしているやつですね笑

AtCoderでは、素数の問題として、素数かどうかを判定する問題、n以下の素数の数を求める問題が出ます。

どのように解くのか（Javaの場合）

自作のライブラリを作り、それを利用する形です。

Javaですが、自分のライブラリはここに置いたので、よかったら参考にしてください。
（バグがあったらすみません。）
github.com

このライブラリを使って、実際に問題を解いてみました。

解いた問題はABC084のD問題 2017-like Number です。
atcoder.jp

高速な素数判定にエラトステネスの篩（ふるい）を使います。

また、累積和も使わないとおそらくTLEします。
（累積和についてはまた今度記事にします。）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		boolean[] isPrime = isPrimeN(100000);

		int[] sum = new int[100001];
		sum[0] = 0;
		for(int i=1; i<=100000; i+=2) {
			if(like2017(i, isPrime))
				sum[i] = sum[i-1] + 1;
			else
				sum[i] = sum[i-1];

			sum[i+1] = sum[i];
		}

		int Q = sc.nextInt();
		for(int i=0; i<Q; i++) {
			int l = sc.nextInt();
			int r = sc.nextInt();

			System.out.println(sum[r]-sum[l-1]);
		}

	}

	public static boolean like2017(int n, boolean[] isPrime) {
		if(n % 2 == 0)
			return false;

		if(isPrime[n] && isPrime[(n+1)/2])
			return true;
		else
			return false;
	}

	//n以下のすべての数の高速な素数判定(エラトステネスの篩)
	public static boolean[] isPrimeN(int n) {

		boolean[] isPrime = new boolean[n+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;

		int sqrt = (int)Math.sqrt(n);

		//割れる数はsqrt以下
		for(int i=2; i<=sqrt; i++) {
			if(isPrime[i]) {
				for(int j=i*i; j<=n; j+=i) {
					isPrime[j] = false;
				}
			}
		}

		return isPrime;
	}

}

これは緑diffですが、やはり緑くらいになってくると、複数の知識を組み合わせた問題が多いですね。

あと、あまり関係ないんですが、Arrays.fillなんて便利なものがあったんですね・・・。

今度から使っていきたいと思います。

というわけで、素数についての記事でした。

本日もABCがあるので、頑張りたいと思います。

Web開発についての記事は次回か次々回には記事にしたいと思います。