0

次のプログラムは、非常に大きな数（600,851,475,143など）のすべての素数を計算します。デストラクタがアプリケーションをクラッシュさせている場合を除いて、これまでのところすべてが正しく機能しています。誰かが私のアプリケーションに何か問題があるのを見ることができますか？私の解決策を再確認した後、答えは間違っていますが、質問はまだ有効です。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stdexcept>
#include <climits>

typedef std::vector<unsigned long long>::const_iterator prime_it;

#define MAX_COL 900000

struct large_vector
{
public:
  large_vector(unsigned long long size, unsigned int row) :
    m_Row(row)
  {
    m_RowVector.reserve(size);
  }
  std::vector<bool> m_RowVector;
  unsigned int m_Row;
};

struct prime_factor
{
public:
  prime_factor(unsigned long long N);
  ~prime_factor() {}
  void print_primes();
private:
  std::vector<bool> m_Primes;
  std::vector<large_vector>m_Vect_Primes;
  unsigned long long m_N;
};

prime_factor::prime_factor(unsigned long long N) :
  m_N(N)
{
  // If number is odd then we need the cieling of N/2 / MAX_COL
  int number_of_vectors = (m_N % MAX_COL == 0) ? (m_N / MAX_COL) : ((m_N / MAX_COL) + 1);
  std::cout << "There will be " << number_of_vectors << " rows";
  if (number_of_vectors != 0) {
    for (int x = 0; x < number_of_vectors; ++x) {
      m_Vect_Primes.push_back(large_vector(MAX_COL, x));
    }

    m_Vect_Primes[0].m_RowVector[0] = false;
    m_Vect_Primes[0].m_RowVector[1] = false;
    unsigned long long increment = 2;
    unsigned long long index = 0;
    while (index < m_N) {
      for (index = 2*increment; index < m_N; index += increment) {
        unsigned long long row = index/MAX_COL;
        unsigned long long col = index%MAX_COL;
        m_Vect_Primes[row].m_RowVector[col] = true;
      }
      while (m_Vect_Primes[increment/MAX_COL].m_RowVector[increment%MAX_COL]) {
        increment++;
      }
    }
  }
}

void prime_factor::print_primes()
{
  for (int index = 0; index < m_N; ++index) {
    if (m_Vect_Primes[index/MAX_COL].m_RowVector[index%MAX_COL] == false) {
      std::cout << index << " ";
    }
  }
}

/*!
 * Driver
 */
int main(int argc, char *argv[])
{
  static const unsigned long long N = 600851475143;
  prime_factor pf(N);
  pf.print_primes();
}

更新 これは動作するバージョンであると確信しています。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stdexcept>
#include <climits>

typedef std::vector<unsigned long long>::const_iterator prime_it;

#define MAX_COL 900000

struct large_vector
{
public:
  large_vector(unsigned long long size, unsigned int row) :
    m_Row(row)
  {
    m_RowVector.resize(size);
  }
  std::vector<bool> m_RowVector;
  unsigned int m_Row;
};

struct prime_factor
{
public:
  prime_factor(unsigned long long N);
  ~prime_factor() {}
  void print_primes();
private:
  std::vector<bool> m_Primes;
  std::vector<large_vector>m_Vect_Primes;
  unsigned long long m_N;
};

prime_factor::prime_factor(unsigned long long N) :
  m_N(N)
{
  // If number is odd then we need the cieling of N/2 / MAX_COL
  int number_of_vectors = (m_N % MAX_COL == 0) ? ((m_N/2) / MAX_COL) : (((m_N/2) / MAX_COL) + 1);
  std::cout << "There will be " << number_of_vectors << " rows";
  if (number_of_vectors != 0) {
    for (int x = 0; x < number_of_vectors; ++x) {
      m_Vect_Primes.push_back(large_vector(MAX_COL, x));
    }

    m_Vect_Primes[0].m_RowVector[0] = false;
    m_Vect_Primes[0].m_RowVector[1] = false;
    unsigned long long increment = 2;
    unsigned long long index = 0;
    while (index < m_N) {
      for (index = 2*increment; index < m_N/2; index += increment) {
        unsigned long long row = index/MAX_COL;
        unsigned long long col = index%MAX_COL;
        m_Vect_Primes[row].m_RowVector[col] = true;
      }
      increment += 1;
      while (m_Vect_Primes[increment/MAX_COL].m_RowVector[increment%MAX_COL]) {
        increment++;
      }
    }
  }
}

void prime_factor::print_primes()
{
  for (unsigned long long index = 0; index < m_N/2; ++index) {
    if (m_Vect_Primes[index/MAX_COL].m_RowVector[index%MAX_COL] == false) {
      std::cout << index << " ";
    }
  }
}

/*!
 * Driver
 */
int main(int argc, char *argv[])
{
  static const unsigned long long N = 400;
  prime_factor pf(N);
  pf.print_primes();
}
4

1 に答える 1

3

リザーブの使用法が正しくありません。

m_RowVector.reserve(size);

ここでm_RowVectorは、ベクトルを再割り当てせずに拡張できるように、スペースが予約されています。ただし、のサイズm_RowVectorはまだ0であるため、要素へのアクセスは未定義です。resize()またはを使用して配列のサイズを変更し、push_back()要素をベクトルに配置する必要があります。

何も悪いことはわかりませんが、ベクトルの問題の終わりを超えて他のインデックスがあると確信しています。operator []の使用をメソッドat（）に変更します。これにより、ベクトルの最後の要素にアクセスしたときに例外がスローされ、エラーの実際の場所の手がかりが得られます。

于 2012-04-14T02:47:37.023 に答える