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 回答