篩法——求n以內(nèi)質(zhì)數(shù)個(gè)數(shù)
int prime[Max];
bool flag[Max];
int EulerSieve(int n)
{
? ? int p=0;
? ? for(int i=2; i<=n; i++)
? ? {
? ? //記錄質(zhì)因數(shù)i。
? ? ? ? if(flag[i]==0)
? ? ? ? ? ? prime[p++]=i;
? ? //篩掉i的倍數(shù)(無(wú)論i為質(zhì)數(shù)還是合數(shù))
? ? ? ? for(int j=0; j<p&&i*prime[j]<=n; j++)
? ? ? ? {
? ? ? ? ? ? flag[i*prime[j]]=1;
? ? ? ? //如果i%prime[j]為0挥下，即 i的質(zhì)因數(shù)為prime[i],也即 i的最小質(zhì)因數(shù)為prime[i].
? ? ? ? //則其后 i的倍數(shù)為prime[j]的倍數(shù)。也就無(wú)須重復(fù)標(biāo)記了。
? ? ? ? ? ? if(i%prime[j]==0)
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? return p;
}
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明虏冻。
本文鏈接：https://blog.csdn.net/qq_30603195/article/details/86677762
