如何計算不超過n的素數的個數？

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

;//初值賦為0cout<<"請輸入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的數{F[r]=1;r+=i;}}for(i=n;i>=2;i--)if(F[i]==0){cout<<"在1-n中最大的質數是："<<i<<endl;break;}system("PAUSE");return0;}