[yukicoder] No.407 鴨等素数間隔列の数え上げ - ヤマカサのプログラミング勉強日記

問題

問題の内容はそこまで難しくありませんでしたが、素数の求め方が悪くTLEとなってしまいました。

考え方

ある数 $N$ が素数かどうかを調べるには、 $\sqrt{N}$ までの数が $N$ を割り切るかどうかを調べれば良いんですが、 $N$ 以下の数が素数かどうかを調べるには、エラトステネスの篩を使うことが適切だと思います。

コード

import java.util.Scanner;

public class Exec0407 {
    static boolean[] isPrime;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int L = scan.nextInt();
        scan.close();
        int max = L / (N -1);
        isPrime = new boolean[max + 1];
        long cnt = 0;
        if(max >= 2) {
            aryPrime();
        }

        for(int i = 2; i < max + 1; i++) {
            if(isPrime[i]) {
                cnt += L - (N - 1) * i + 1;
            }
        }
        System.out.println(cnt);
    }
    static void aryPrime(){
        int l = isPrime.length;
        for(int i = 0; i < l; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2; i <= (int)Math.sqrt(l); i++) {
            if(isPrime[i]) {
                for(int j = i * 2; j < l; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}

感想

エラトステネスの篩という名前は知っていましたが、使用したことはなかったので、載せました。

それと、出題者さんのアイコンが可愛いですね。