Project Euler - Problem 200

Find the 200th prime-proof sqube containing the contiguous sub-string "200"

Problem 200 (日本語訳)

p²q³ (p, q は異なる素数)で表せる数をスキューブ(sqube)と定義する. 例えば, 200 = 5²2³, 120072949 = 23²61³ である.

最初の5つのスキューブは 72, 108, 200, 392, 500 である.

面白いことに, 200はどの1桁の数字を変更しても素数とならない最小の数である. この特徴をもつ数字を"耐素数性のある"(prime-proof)数と呼ぶ. 連続する部分文字列に "200" を持つ次の耐素数性のあるスキューブは 1992008 である.

連続する部分文字列に "200" を持つ 200 番目の耐素数性のあるスキューブを求めよ.

[訳注: sqube(スキューブ): square(平方数)とcube(立方数)からの造語]

(日本語訳より)

200 問目だからかやたらと 200 を出してきて草

やってみたらやるだけだった

ある程度の大きさまでの素数を生成して，ある程度の大きさ以下のスキューブを列挙して，"200" が含まれているかどうか調べて，耐素数性のあるものをピックアップして，200 番目の要素を答えて，終わり

ABC の D 問題くらい？

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(), (x).end()



#define MAX 1000000
#define MMAX 1000000000000LL
vector<int> ps;
bool p[MAX + 1];
vector<ll> squbes;


inline ll sqube(ll p, ll q) { return p * p * q * q * q; }

bool is_prime(ll n)
{
    ll 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;
}

bool primeproof(ll n) {
    ll x = n, y, d = 1;
    while (x) {
        ll r = x % 10 * d;
        x /= 10;
        y = n - r;

        for (ll z = y, c = 0; c < 10; z += d, c++) {
            if (z <= MAX) {
                if (p[z]) return false;
            }
            else {
                if (is_prime(z)) return false;
            }
        }
        d *= 10;
    }
    return true;
}

bool contain200(ll n) {
    while (n) {
        if (n % 1000 == 200) return true;
        n /= 10;
        while (n % 100) n /= 10;
    }
    return false;
}

int main()
{
    clock_t start, end;
    start = clock();

    //cin.tie(0);
    //ios::sync_with_stdio(false);

    Fill(p, true);
    p[0] = p[1] = false;
    for (int i = 2; i * i <= MAX; i++) if (p[i]) for (int j = i * i; j <= MAX; j += i) p[j] = false;
    REP(i, MAX) if (p[i]) ps.push_back(i);

    for (int i = 0; i < ps.size(); i++) {
        for (int j = 0; j < ps.size(); j++) {
            if (i == j) continue;
            ll sqb = sqube(ps[i], ps[j]);
            if (sqb > MMAX) break;
            squbes.push_back(sqb);
        }
    }
    
    sort(all(squbes));
    
    int count = 0;
    REP(i, SZ(squbes)) if (contain200(squbes[i]) && primeproof(squbes[i])) {
        count++;
        if (count == 200) {
            cout << squbes[i] << endl;
            break;
        }
    }
    
    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}