TopCoder SRM 471 Div2 Easy PrimeContainers

問題概要

ある数Nが与えられたとき、N/2^k（kは任意の自然数、余りは切り捨て）の形で表される素数はいくつあるかを求めよ。
N≦1000000である。

解法

2ずつ割って素数かどうか調べればよい。
素数かどうかのチェックにはエラトステネスの篩を使うのが定番。試し割りしていっても時間間に合うような気もするけれど。。。（Nまで割ると危ないかな？）

ソースコード

class PrimeContainers {
	public:
	int containerSize(int N) 
	{
		for(int i=2;i*i<MX;i++)if(!p[i])for(int j=i+i;j<MX;j+=i)p[j]=1;
		p[0]=p[1]=1;
		
		int ans=0;
		for(;N;N/=2)ans+=!p[N];
		
		return ans;
	}
};