Problem 41 Pandigital prime （暴力set+vector）

分手后的思念是犯贱 2022-07-15 02:41 113阅读 0赞

## Pandigital prime ##

### Problem 41 ###

We shall say that an *n*\-digit number is pandigital if it makes use of all the digits 1 to *n* exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest *n*\-digit pandigital prime that exists?

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td> 
        <div style="text-align:right"> 
         <span style="font-size:18px">Answer:</span> 
        </div> </td> 
       <td><strong><span style="font-size:18px">7652413</span></strong></td> 
      </tr> 
      <tr> 
       <td colspan="2"><span style="color:rgb(153,153,153)"><span style="font-size:18px">Completed on Sun, 30 Oct 2016, 06:32</span></span></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
 </tbody> 
</table>

代码：

#include<bits/stdc++.h>
    using namespace std;
    int is_pandigital(long long n)
    {
        if(n<=0) return 0;
     
        vector<int> v;         
        while(n != 0)
        {
            v.push_back(n%10);
            n/=10;
        }
     
        set<int> set_n(v.begin(),v.end()); //转化为set，去重
     
        int len = v.size();
        if(set_n.size() == len)                 //不含重复值
        {
            sort(v.begin(),v.end());         //默认从小到大排序
            for (int i=0;i<len;i++)             //digits=1,2,3...
            {
                if (v[i] != (i+1))         
                {
                    return 0;
                }
            }
            return 1;
        }
        return 0;
    }
    
    int is_prime(long long n)
    {
            if (n == 2)
                    return 1;
            if (n % 2 == 0)
                    return 0;
    
            long long i;
            for (i = 3; i * i <= n; i += 2)
                    if (n % i == 0)
                            return 0;
            return 1;
    }
    
    int main()
    {
            long long n;
            for (n = 7654321; n >= 1234567; n -= 2)
                    if (is_pandigital(n) && is_prime(n)) break;
            printf("%lld\n", n);
            return 0;
    }