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