Prime

#include <string.h>

#include <list>

class Prime {
  char *_notprime;
  int *_seq;
  int _total_prime;
  int _range;
 public:
  Prime(int n) {
    _range = n;
    _notprime = new char[n + 1];
    _seq = new int[n + 1];
    memset(_notprime, 0, sizeof(*_notprime)*(n+1));
    _notprime[0] = _notprime[1] = 1;
    _total_prime = 0;
    for (int i = 2; i <= n; ++i) {
      if (!_notprime[i])
        _seq[_total_prime++] = i;
      for (int j = 0; j < _total_prime; ++j) {
        if (i * _seq[j] > _range) break;
        _notprime[i * _seq[j]] = true;
        if (i % _seq[j] == 0) break;
      }
    }
  }
  ~Prime() {
    delete[] _notprime;
    delete[] _seq;
  }
  bool IsPrime(int n) const {return !_notprime[n];}
  int GetPrime(int k) const {return k < _total_prime ? _seq[k] : 0;}
  int* GetPrimes() const {return _seq;}
  int GetTotalPrimes() const {return _total_prime;}
  int GetRange() const {return _range;}
  std::list<std::pair<int, int> > Decompose(int n) {
    std::list<std::pair<int,int> > res;
    int i = 0;
    while (n != 1) {
      int p = GetPrime(i);
      if (n % p) {
        ++i;
        continue;
      }
      res.push_back(std::make_pair(p, 0));
      while (n % p == 0) {
        ++res.back().second;
        n /= p;
      }
    }
    return res;
  }
};

#include <iostream>

using namespace std;

int main() {
  Prime p(1000000);
  for (int i = 0; i < 30; ++i) {
    cout << p.GetPrime(i) << "\t";
  }
  cout << endl;

  auto fact = p.Decompose(54321);
  for (auto x: fact) {
    cout << x.first << " " << x.second << endl;
  }
  return 0;
}