山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.407 鴨等素数間隔列の数え上げ

問題

No.407 鴨等素数間隔列の数え上げ - yukicoder

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

考え方

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

演習(エラトステネスの篩)の回答例 - CourseWiki

コード

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;
                }
            }
        }
    }
}

感想

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

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