Eratosthens sieve

4785 ワード



#include <iostream>
#include <set>

using namespace std;

#include "IO.hpp"

void SIEVE(set<int>& primes,int limit){

  int index;

  primes.erase(primes.begin(),primes.end());

  for(int i=2;i<limit;i++)
    primes.insert(i);

  for(int i=2;i*i<=limit;i++)
    if(primes.find(i) != primes.end()){

      index = 2*i;
      while(index <= limit){
        primes.erase(index);
        index += i;
      }
    }

  return;
}

int main(int argc,char *argv[])
{
  set<int> primeSet;

  set<int>::iterator iter;
  int primeLimit,count=0;

  cout<<"Enter upper limit for the set of primes: ";
  cin>>primeLimit;
  cout<<endl;

  SIEVE(primeSet,primeLimit);

  iter= primeSet.begin();

  writeContainer(primeSet.begin(),primeSet.end()," ",10);

  cout<<endl;

  return 0;
}


#ifndef _IO_HPP_
#define _IO_HPP_

#include <vector>
#include <set>
#include <list>

using namespace std;

//LINE=0     
//separator           
//N     

//writeArray      (arr[],     N:,        separator,  LINE)
//writeContainer  (begin(),   end(),     separator,  LINE)
//writeVector     (vector<T>, separator, LINE)
//writeList       (list<T>,   separator, LINE)
//writeSet        (set<T>,    separator, LINE)



template <typename T>
void writeArray(const T arr[],                  \
                int N,                          \
                const char* separator,          \
                int LINE){

	for(int i=0;i<N;i++){

		cout<<arr[i]<<separator;

    if(LINE!=0)
      if(i%LINE==0)
        cout<<endl;
  }
	cout<<endl;

  return;
}

template <typename T>
void writeVector(const vector<T>& v,            \
                 const char* separator,         \
                 int LINE){

	int i, n = v.size();

	for(i=0;i<n;i++){

		cout<<v[i]<<separator;

    if(LINE!=0)
      if(i%LINE==0)
        cout<<endl;
  }
	cout<<endl;

  return;
}

template <typename T>
void writeList(const list<T>& alist,            \
               const char* separator,           \
               int LINE){

	typename list<T>::const_iterator iter;

  int count = 0;
  iter = alist.begin();

  while(iter != alist.end()){

    count++;
		cout<<*iter<<separator;

    if(LINE!=0)
      if(count%LINE==0)
        cout<<endl;

    iter++;
  }
  cout<<endl;

  return;
}

template <typename T>
void writeSet(const set<T>& alist,              \
              const char* separator,            \
              int LINE){

	typename set<T>::const_iterator iter;

  int count = 0;
  iter = alist.begin();

  while(iter != alist.end()){

    count++;
		cout<<*iter<<separator;

    if(LINE!=0)
      if(count%LINE==0)
        cout<<endl;

    iter++;
  }
  cout<<endl;

  return;
}

template <typename Iterator>
void writeContainer(Iterator begin,             \
                    Iterator end,               \
                    const char* separator,      \
                    int LINE){

	Iterator iter = begin;
  int count = 0;

	while (iter!=end){

    count++;
		cout<<*iter<<separator;

    if(LINE!=0)
      if(count%LINE==0)
        cout<<endl;

		iter++;
	}
  cout<<endl;

  return;
}

#endif


このふるいの実現は簡単で、例えば上限が300で300以内のすべてのsqrt(300)より小さい質量数の倍数を切り落とせばいい.私のところはsqrt(300)より小さい質量数の倍数を切り落とせばいい.sqrt(300)より小さい質量数を切り落とせばいいから、このふるいを2つ使えばいい.
例えば10,000以内をふるい100以内の素数にして100以内の素数を切り落とせばいいのですが、100の数字を引かなくても時間が節約できます
SPOJのヒントに従って、ふるい法を使って、二次ふるいはすべてSPOJの第2題を通過することができなくて、すべてタイムアウトです.
もしかすると私のふるい法の書く性能はset容器の性能のようではありません確かに問題があるかもしれません