TopCoder Open 2010 Round 3 Easy. SieveOfEratostheness

問題概要

maxNumまでの数に対してエラトステネスの篩を行ったとき、
最後に消去される合成数を求めよ。
maxNum≦10^9を満たす。

解法

エラトステネスで最後に消去するのはsqrt(maxNum)以下で最大の素数の倍数。


sqrt(maxNum)以下で最大の素数をPと置くと、
P*(P未満の素因数をもつ数)は既に消去されているので、消去されていない数はPの倍数のうち、P未満の素因数を持たない数。


Pの倍数はせいぜいsqrt(maxNum)個程度なので全部についてP未満の素数で割れないかどうか試せばよい。

ソースコード

vi prime;
bool p[50000];

bool ok(int t,int mxfct)
{
	rep(i,mxfct)if(t%prime[i]==0)return 0;
	return 1;
}

class SieveOfEratosthenes {
	public:
	int lastScratch(int maxNum)
	{
		p[0]=p[1]=1;
		for(int i=2;i*i<50000;i++)if(!p[i])for(int j=i*i;j<50000;j+=i)p[j]=1;
		prime.clear();
		rep(i,50000)if(!p[i])prime.pb(i);
		
		int sq=(int)sqrt(maxNum);
		int mxfct=lower_bound(all(prime),sq)-prime.begin();
		if(prime[mxfct]>sq)mxfct--;
		
		int tmp=prime[mxfct],ans=prime[mxfct];
		for(;tmp<=maxNum;tmp+=prime[mxfct])
		{
			if(ok(tmp,mxfct))ans=tmp;
		}
		
		return ans;
	}
};