Project Euler - Problem 293

Pseudo-Fortunate Numbers

偶数の正整数 N は 2 の累乗であるか素因数が全て連続した素数である場合, 許容的(admissible)と呼ぶ.
最初の 12 個の許容的な数は 2,4,6,8,12,16,18,24,30,32,36,48 である.

N が許容的であれば, N+M が素数である最小の整数 M > 1 を N の擬似フォーチュン数(pseudo-Fortunate number)と呼ぶ.

例えば, N=630 は許容的である, 630 は偶数でその素因数は連続する素数 2, 3, 5, 7 であるからだ.
631 より大きい次の素数は 641 である, つまり 630 の擬似フォーチュン数は M=11 である. 16 の擬似フォーチュン数は 3 であることがわかる.

10⁹ 未満の許容的な数 N に対して, 全ての異なる擬似フォーチュン数の合計を求めよ.

(日本語訳より)

やるだけ

2 から始まる連続した素数の積が 10⁹ を超えるのは
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230
なので，29 未満の素数を使って再帰で admissible number を見つけてくる．

せいぜい 6000 個程度なので篩を使わず普通に素数判定して終わらせた．

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <functional>
#include <set>
#include <numeric>
#include <stack>
#include <utility>
#include <time.h>
#include <iterator>
//#include "util.h"

using namespace std;
typedef unsigned uint;
typedef long long lint;
typedef unsigned long long ulint;


//呪文
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { cout << "{" << m.first << ", " << m.second << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { cout << "{ }"; return ostr; } cout << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; } cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; }    cout << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { cout << "{ }"; return ostr; } cout << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { cout << ", " << *itr; }    cout << "}"; return ostr; }
//template <typename T> void print(T* v, int N) { if (N == 0) cout << "{ }"; cout << "{" << v[0]; for (int p = 1; p < N; p++) cout << ", " << v[p]; cout << "}"; }
#define PI 3.14159265358979323846
#define EPS 1e-8
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(), (x).end()

#define MAX 1000000000LL

vector<lint> vec;

void rec(lint n = 1, size_t pos = 0) {
    static const lint p[9] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };

    if (pos == 9) return;

    n = n * p[pos];
    if (n < MAX) vec.push_back(n);
    else return;

    rec(n, pos);
    rec(n, pos + 1);
}

bool is_prime(lint n)
{
    lint i;

    if (n < 2) return false;
    if (n == 2) return true;

    if (n % 2 == 0) return false;

    for (i = 3; i * i <= n; i += 2) {
        if (n % i == 0)  return false;
    }
    return true;
}

lint pseudo_fortunate(lint N) {
    for (lint M = 3; ; M += 2) {
        if (is_prime(N + M)) return M;
    }
}

int main() {

    clock_t start, end;
    start = clock();

    rec();
    sort(all(vec));

    set<lint> pf;
    for (int i = 0; i < vec.size(); i++) {
        pf.insert(pseudo_fortunate(vec[i]));
    }

    lint ans = 0;
    for (auto itr = pf.begin(); itr != pf.end(); itr++) ans += *itr;
    cout << ans << endl;

    end = clock();
    printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}

0.6 sec ぐらい．

絶滅

どうでもいい

Project Euler - Problem 293

Pseudo-Fortunate Numbers