Login
Immutable PageDiscussionInfoAttachments

Please use a more selective search term instead of ""

Clear message
iz/競技プログラミング/Project Euler 041 Pandigital prime

MMA

http://projecteuler.net/problem=41

1からnまですべてを各位に持つ数(1234, 4231, 987654321, etc)のうち、最大の素数を求める。

prev_permutationででかい順にブン回す。

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <sstream>
   4 using namespace std;
   5 
   6 typedef long long ll;
   7 
   8 ll to_l(const string &s) {
   9     istringstream is(s);
  10     ll n;
  11     is >> n;
  12     return n;
  13 }
  14 
  15 bool isPrime(ll n) {
  16     for (ll i = 2; i * i <= n; i++) {
  17         if (n % i == 0) {
  18             return false;
  19         }
  20     }
  21     return true;
  22 }
  23 
  24 int main() {
  25     for (int i = 9; i >= 1; i--) {
  26         string s = "";
  27         for (int j = i; j >= 1; j--) {
  28             s.push_back(j + '0');
  29         }
  30         do {
  31             ll n = to_l(s);
  32             if (isPrime(n)) {
  33                 cout << n << endl;
  34                 return 0;
  35             }
  36         } while (prev_permutation(s.begin(), s.end()));
  37     }
  38     return 0;
  39 }