开心程序吧

质数问题- -

                                      

质数问题:求1——3000的质数!
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int intSqrt(int n){
  int ans = n/2, tmp = n;
  while(tmp > ans){
    tmp = ans;
    ans = (tmp + n / tmp) /2;
  }
  return tmp;
}

void count_prime(int range){
  int limit=(range-1)/2, i, j, k=-1, l, s, t,
    bound=(intSqrt(range)-1)/2, count=4;
  const int pn[96] = {1, 2, 1, 2, 3, 1, 3, 2, 1, 2, 3, 3, 1, 3, 2, 1,
                      3, 2, 3, 4, 2, 1, 2, 1, 2, 4, 3, 2, 3, 1, 2, 3,
                      1, 3, 3, 2, 1, 2, 3, 1, 3, 2, 1, 2, 1, 5, 1, 5,
                      1, 2, 1, 2, 3, 1, 3, 2, 1, 2, 3, 3, 1, 3, 2, 1,
                      3, 2, 3, 4, 2, 1, 2, 1, 2, 4, 3, 2, 3, 1, 2, 3,
                      1, 3, 3, 2, 1, 2, 3, 1, 3, 2, 1, 2, 1, 5, 1, 5};
  char *data = new char[limit+1];
  for(i=1;i<=limit;++i) data[i] = 1;
  clock_t start = clock();
  for(i=4;i<=limit;i+=3) data[i] = 0;
  for(i=12;i<=limit;i+=5) data[i] = 0;
  for(i=24;i<=limit;i+=7) data[i] = 0;
  for(i=5;i<=bound;i+=pn[k]){
    if(data[i]){
      t = i*(i+i+2), s = i+i+1, j=k+1, l=k+48;
      while(true){
        if(data[t]!=0) data[t] = 0;
         if((t+=s*pn[j]) > limit) break;
        if(++j>l) j = k+1;
      }
    }
    if(++k==48) k = 0;
  }
  k = -1;
  for(i=5;i<=limit;i+=pn[k])  {
    if(data[i]) ++count;
    if(++k==48) k = 0;
  }
  /*for(i=1;i<=limit;i++)
    if(data[i]) cout << ", " << (i+i+1);*/
  cout << "\nIt takes " << float(clock()-start)/CLOCKS_PER_SEC
    << " seconds." << endl;
  cout << "There are totally: " << count << " primes." << endl;
  delete [] data;
}


void main(int argc, char* argv[]){
  int range = argc > 1 ? atoi(argv[1]) : 100;
  count_prime(range);
}

- 作者： 刘加开 2005年03月20日, 星期日 15:04 加入博采