Codeforces #191, B : Hungry Sequence

問題文

http://codeforces.com/contest/327/problem/B

概要

次の条件を満たす数列を Hungry Sequence と呼ぶ。

• を満たす i, j について
• を満たす i, j について

整数 n が与えられるので、n 項からなる Hungry Sequence を一つ求めよ。

解法

素数を昇順に並べることで、両方の条件をクリアできます。
十分な長さの素数列を予め生成して、n 項を出力すればよいです。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

// Eratosthenes の篩（素数かどうかの表が返る）
vector<bool> eratosthenes( int n )
{
	vector<bool> nums( n + 1, true );
	nums[0] = nums[1] = false;

	for ( int i = 0; i < nums.size(); ++i )
	{
		if ( !nums[i] )
		{
			continue;
		}

		for ( int j = 2; i * j < nums.size(); ++j )
		{
			nums[ i * j ] = false;
		}
	}

	return nums;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	VI primes;
	{
		auto isPrime = eratosthenes( 1300000 );
		REP( i, 2, isPrime.size() )
		{
			if ( isPrime[i] )
			{
				primes.PB( i );
			}
		}
	}

	int n;
	cin >> n;

	REP( i, 0, n )
	{
		if ( i )
		{
			cout << ' ';
		}
		cout << primes[i];
	}
	cout << endl;

	return 0;
}