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

問題

問題概要

数列の隣合う数字の間隔が素数で表されるとき、すべてでいくつの数列が構成できるか求める問題。

解法

入力が5 12の時を考える。
素数2の時
0 2 4 6 8
1 3 5 7 9
2 4 5 8 10
3 5 7 9 11
4 6 8 10 12
上のような4つの数列が存在する。 このとき数列の末項が最小となるのは8の時で、L=12より末項は12まで許容される。初項を1つずつずらせば素数2の時の数を求めることができる。 これらの処理をnagasaを利用して行っている。

ミス

素数列挙が足りてなくてWA

コード

#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

bool isprime[20000010];//trueならiは素数
//エラトステネス
void eratos(int m){
    for (int i = 0; i <= m; ++i) isprime[i] = true;
    isprime[0] = isprime[1] = false;
    //iを残してiの倍数を消していく
    for (int i = 2; i <= m; ++i){
        if(isprime[i]){
            for (int j = 2 * i; j <= m; j += i){
                isprime[j] = false;
            }
        }
    }
    return;
}

int main(void){
    int n, l; cin >> n >> l;
    eratos(20000000);//素数をあらかじめ求めておく。

    ll ans = 0;//答えを入れる
    n--;
    ll p = 2;
    while(n * p <= l){
        if(isprime[p]){
            ll nagasa = n * p;//素数pの時の(数列の末項) - (数列の初項)
            //nagasaを利用して、素数pの間隔で表される数列の個数が求まる。
            ans += (l - nagasa + 1);
        }
        p++;
    }
    cout << ans << endl;
    return 0;
}