1

間違いを見つけるのに何時間も費やしましたが、成功しませんでした:( オイラー
の問題を解く: 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;
}

前もって感謝します！

4

1 に答える 1

0

この問題は SO で何度も解決されています。「[c++] プライム オイラー」を検索します。

証拠は、forループ の終了条件によって与えられます。

sqrt(upper_bound - lower_bound)

primes[]あなたの投稿には の定義が見つかりません。range関数はそれにアクセスしますが、パラメーターを介して提供されたり、primes関数内で配列が宣言されたりしません。

SO や Web を検索すると、多くの情報を得ることができます。投稿する前にそれを試してください。

于 2012-11-21T18:55:39.600 に答える