以下程序计算真正大数(例如 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();
}