SRM471 Div1 Easy(250) PrimeSequences

PrimeSequences

問題文の通りに調べるだけ。素数かどうかの表さえ事前に計算しておけば充分間に合う。

#include <vector>

using namespace std;

class PrimeSequences
{
public:
    int getLargestGenerator( int N, int D );
};

int PrimeSequences::getLargestGenerator( int N, int D )
{
    vector<bool> prime( N+1, true );
    prime[0] = prime[1] = false;
    for ( int i=0; i<=N; i++ )
        if ( prime[i] )
            for ( int j=i+i; j<=N; j+=i )
                prime[j] = false;

    for ( int X=N; X>=0; X-- )
    {
        int c = 0;
        int t = X;
        while ( prime[t] )
            t /= 2,
            c++;

        if ( c >= D )
            return X;
    }

    return -1;
}