用筛选法求N以内的素数

Question

#include <stdio.h>
int main()
{
//
随机输入整数N
采用筛选法
输出N以内的素数
//
return 0;
}

Answer 1

#include <iostream>
#include <cmath>
using namespace std;

#define N 100
bool isPrime[N];

bool Prime(int n)
 {
     if (n<2)
     {
         return false;
     }
     if (n==2)
     {
         return true;
     }
     int upper=sqrt(static_cast<double>(n));
     for (int i=2;i<=upper;i++)
     {
         if (n%i==0)
         {
             return false;
         }
     }
     return true;
 }
 int main()
 {
     isPrime[0]=isPrime[1]=false;
     isPrime[2]=true;
     int i=2;
     for (int i=3;i<N;i++)
     {
         if ((i&(0x01)) ==0)    //用位运算代替i%2==0
         {
             isPrime[i]=false;
         }
         else
         {
             isPrime[i]=true;
         }
     }
     int upper=sqrt(static_cast<double>(N));
     for(int i=3;i<upper;i+=2)
     {
         if (isPrime[i] && Prime(i))
         {
             for (int j=i+i;j<N;j+=i)
             {
                 isPrime[j]=false;
             }
         }
     }
     int count=0;
     for (int i=0;i<N;i++)
     {
         if (isPrime[i])
         {
             cout<<i<<"  ";
             count++;
         }
     }
     cout<<endl;
     cout<<"素数个数为:"<<count<<endl;

     //最原始的求素数方法，速度很慢
     //int count=0;
     //for (int i=2;i<N;i++)
     //{
     //    if (Prime(i))
     //    {
     //        count++;
     //    }
     //}
     //cout<<count<<endl;
     return 0;
 }