Alphametic Prime

Solution by dudu — 100 pts

Code / Notes

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

int main() {
    string S;
    cin >> S;

    // Complexidade? O(N*log(log(N)))
    vector<bool> P(1e7, true);
    P[0] = P[1] = false;
    for (int i = 2; i < P.size(); i++) {
        if (!P[i]) continue;
        for (int j = 2*i; j < P.size(); j += i) {
            P[j] = false;
        }
    }

    for (int i = 0; i < P.size(); i++) {
        if (!P[i]) continue;
        string num = to_string(i);
        if (S.size() != num.size()) continue;

        // Checo se o formato ta certo:
        bool ok = true;
        for (int i = 0; i < S.size(); i++) {
            for (int j = 0; j < S.size(); j++) {
                if ((S[i] == S[j]) != (num[i] == num[j]))
                    ok = false;
            }   
        }
        if (ok) {
            cout << num << endl;
            exit(0);
        }
    }

    cout << -1 << endl;
}

Last updated 1 month ago

« Back to problem