如何計(jì)算不超過n的素?cái)?shù)的個(gè)數(shù)？

用篩選法，令F初值為0，從i=2開始，若F(i)=0,則將1-n內(nèi)所有i的倍數(shù)（除i以外）的F賦為1，否則跳過，然后由n向1找出第一個(gè)F為0的數(shù)字，則該數(shù)字為所求（時(shí)間效率O（2n），空間效率O(n)，較枚舉每個(gè)數(shù)字并判斷更快）附C++代碼#include<cstdlib>#include<iostream>usingnamespacestd;intmain(intargc,char*argv[]){intF[1000000],i,r;intn;memset(F,0,sizeof(F))

;//初值賦為0cout<<"請(qǐng)輸入n"<<endl;cin>>n;for(i=2;i<=n;i++){if(F[i]==1)continue;//如果F為1，跳過r=i*2;//從2倍開始while(r<=n)//找小于n的數(shù){F[r]=1;r+=i;}}for(i=n;i>=2;i--)if(F[i]==0){cout<<"在1-n中最大的質(zhì)數(shù)是："<<i<<endl;break;}system("PAUSE");return0;}