Круговое простое, помогите найти ошибку, Переполнение стека

Потратил час, пытаясь найти ошибку, не удалось 🙁
Решение проблемы Эйлера: http://projecteuler.net/problem=35
Кажется, в данный момент у меня не работает голова

Код не оптимизирован, извините за это (что я тут не так делаю?)
Правильный ответ 55, моя программа дает мне 22

#include "euler.hpp"#include <algorithm>

int main() {
euler::prime_generator<euler::eratosthenes_sieve> gen;
gen.range(0, 1000000);
unsigned c = 0; // number of circular primes
unsigned p = 0; // number of primes (test)
unsigned prime;
while(prime = gen.nextPrime()) {
p++;
bool ok = true;
std::vector<unsigned> pv = euler::number2vector(prime);
if(pv.size() > 1) {

bool cont = false;
for(unsigned i = 0; i < pv.size(); ++i) {
if(pv[i] % 2 == 0) { cont = true; break; }
}
if(cont) continue;
std::sort(pv.begin(), pv.end());

do {
if(!gen.isPrime(euler::array2number(&pv[0], pv.size()))) {
// was desperate and made this
if(euler::isPrime(euler::array2number(&pv[0], pv.size()))) {
std::cout << prime << " -> " << euler::array2number(&pv[0], pv.size()) << std::endl;
}
else ok = false;
break;
}
} while(std::next_permutation(pv.begin(), pv.end()));

}
if(ok) {
//std::cout << prime << std::endl;
c++;
}
//std::cout << prime << std::endl;
}

std::cout << p << " -> " << c << std::endl;

euler::pause();
}

Несколько внешних функций я использую

// in class
void range(unsigned lower_bound, unsigned upper_bound) {
m_lower_bound = lower_bound;
primes.resize(upper_bound - lower_bound + 1, true);
for(unsigned i = 0; i < 2 - lower_bound; ++i) primes[i] = false;
for(unsigned i = 2; i <= sqrt(upper_bound - lower_bound); ++i) {
if(primes[i]) {
for(unsigned j = i*i; j <= upper_bound; j += i) {
primes[j] = false;
}
}
}
}
// in the same class
bool isPrime(unsigned number) {
return primes[number - m_lower_bound];
}

// in the same class
unsigned nextPrime() {
for(; next <= m_upper_bound; ++next) {
if(isPrime(next)) return next++ + m_lower_bound;
}
return 0;
}

template <typename T>
T array2number(T * begin, unsigned length) {
T number = 0;
unsigned m = 1;
while(length--) {
number += begin[length] * m;
m *= 10;
}
return number;
}

template <typename T>
std::vector<T> number2vector(T number) {
unsigned l = number_length(number);
std::vector<T> vec(l);
while(l--) {
vec[l] = number % 10;
number /= 10;
}
return vec;
}

Заранее спасибо!

1

Решение

Эта проблема была решена много раз на SO. Ищите «[c ++] prime euler».

Доказательства даны завершающим условием for цикл:

sqrt(upper_bound - lower_bound)

Я не могу найти определение primes[] в вашем посте. range функция обращается к нему, но он не предоставляется через параметры, и не является primes массив объявлен внутри функции.

Вы можете получить много информации, выполнив поиск SO и в Интернете. Попробуйте это перед публикацией.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector