论坛 › 欧拉计划（Project Euler） › 题目41：最大的n位pandigital质数是多少？

欧拉计划 发表于 2015-5-2 11:41:27

题目41：最大的n位pandigital质数是多少？

Pandigital prime

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?
题目：

如果一个数字将 1 到 n 的每个数字都使用且只使用了一次，我们将其称其为一个 n 位的 pandigital 数。例如，2143 是一个 4 位的 pandigital 数，并且是一个质数。

最大的 n 位 pandigital 质数是多少？

迷雾少年 发表于 2016-8-30 13:57:12

本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:38 编辑

1423
2143
2341
4231
1234657
1245763
1246537
1246573
1247563
1254367
1254637
1256347
1257463
1263547
1264537
1264573
1265347
1275643
1276543
1324567
1342567
1342657
1345627
1354267
1356247
1356427
1362457
1425367
1426753
1427563
1427653
1435627
1436257
1436527
1452637
1453267
1463257
1465273
1476253
1476523
1524637
1524763
1532647
1546273
1546327
1562347
1563427
1564237
1572643
1574623
1576243
1624573
1625347
1632457
1634257
1645327
1647253
1647523
1652347
1653427
1672453
1674523
1725463
1726453
1742563
1752643
1764253
2136457
2143567
2145763
2146357
2153647
2156437
2163547
2176543
2315647
2341567
2345617
2347561
2354167
2364517
2365471
2375641
2376541
2413657
2431657
2436517
2436571
2451367
2451637
2456371
2456731
2457361
2457613
2467351
2475163
2476351
2516473
2534671
2536147
2537461
2543617
2546317
2547361
2547613
2547631
2561743
2563147
2563417
2576341
2613547
2631457
2634517
2637451
2637541
2641357
2645371
2647531
2651437
2651743
2653741
2654317
2654371
2657143
2657341
2674513
2674531
2714563
2716453
2716543
2734561
2735641
2736451
2741653
2743561
2745361
2754361
2761453
2761543
2765143
3124567
3124657
3126457
3126547
3145627
3152467
3154267
3156427
3165427
3214567
3214657
3215467
3216457
3241657
3245761
3246157
3246751
3251467
3254761
3256417
3256471
3257641
3261547
3264571
3265741
3412567
3412657
3415627
3421567
3421657
3427561
3451627
3452671
3456127
3456217
3456721
3457261
3461257
3462517
3462751
3465271
3467251
3467521
3475261
3512647
3514267
3516427
3524617
3526147
3526741
3542167
3542761
3546271
3546721
3561247
3562417
3574621
3576421
3612457
3612547
3624157
3627451
3642157
3642571
3672451
3672541
3674521
3675241
3725461
3742561
3746521
3752641
3756241
3756421
3765241
4125637
4125673
4126537
4127653
4135627
4152763
4157623
4165327
4167523
4172653
4175263
4176253
4213567
4216573
4216753
4231567
4235761
4253167
4253617
4253671
4257163
4257613
4261357
4263157
4265137
4265713
4265731
4267531
4271563
4276513
4312657
4321657
4325617
4326571
4356217
4356721
4361257
4362751
4365271
4372651
4375621
4513627
4516327
4521367
4521637
4523671
4526371
4527361
4537261
4561237
4561327
4561723
4562317
4562731
4563127
4563217
4563271
4567231
4571263
4572163
4621537
4625713
4631527
4637251
4652173
4652317
4657123
4657321
4672531
4675123
4712563
4716253
4721653
4723561
4725613
4725631
4732561
4752361
4765213
5123467
5126347
5126437
5136427
5142637
5143267
5146237
5162473
5162743
5164273
5164723
5172463
5176243
5214367
5214637
5214763
5216473
5231647
5234167
5236741
5237641
5241673
5243167
5243761
5246173
5246713
5247163
5261743
5263417
5264137
5264173
5267341
5267413
5271463
5274163
5274631
5276431
5312467
5321467
5321647
5327461
5341627
5342167
5342761
5346127
5347621
5361247
5364127
5367421
5376421
5421673
5421763
5423167
5423617
5426173
5426371
5426713
5431627
5436127
5436217
5436271
5436721
5461273
5461723
5462137
5462173
5463217
5463721
5472613
5472631
5473261
5476213
5614327
5621437
5624137
5624317
5624713
5627143
5631427
5632741
5634217
5634721
5641327
5643217
5647231
5647321
5672341
5672413
5674231
5723461
5724163
5724613
5726143
5726341
5734621
5742361
5742631
5746123
5746231
5761423
5762143
5762413
5763421
6124753
6134257
6142573
6145273
6145327
6145723
6152743
6154273
6154723
6174253
6175243
6175423
6214357
6214573
6214753
6215347
6217543
6234517
6235147
6235417
6235741
6241537
6243157
6245731
6251347
6251743
6257143
6257431
6274531
6275341
6312547
6321457
6325471
6342157
6342517
6345127
6345271
6345721
6347521
6352147
6352741
6354217
6415237
6421573
6423517
6423751
6435127
6435721
6437521
6451723
6452137
6453721
6457123
6472351
6472513
6473251
6475321
6512347
6512437
6513427
6514327
6524137
6527413
6541723
6542713
6543127
6547213
6572143
6572413
6572431
6574231
6714523
6724351
6725143
6732541
6734521
6745231
6751243
6754213
7124653
7125463
7126453
7126543
7142563
7145623
7152643
7164253
7165423
7215643
7216453
7216543
7234651
7245361
7246513
7253461
7253641
7256341
7264351
7264513
7264531
7324561
7324651
7352461
7354261
7356421
7362541
7412563
7412653
7415623
7421563
7425361
7425631
7426351
7432651
7435621
7451263
7451623
7452163
7456231
7456321
7462513
7514623
7524631
7526143
7536241
7536421
7541623
7542163
7546321
7561423
7562341
7562413
7562431
7564231
7621543
7624531
7625143
7625341
7641253
7642513
7652413
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
//是否质数

//这个数
bool is(int num,int n)
{
        string temp;
        //拼出一个n位的pandig数
        for (int i=1;i<=n;i++)
        {
                char buf;
                itoa(i,buf,10);
                temp+=buf;
        }
        //加入这个有n位的数字 把1-n都使用了 那么排序后 肯定和temp相等
        char buf;
        itoa(num,buf,10);
        string g(buf);
        sort(g.begin(),g.end());
        return g==temp;

}
//获取一个数字的位数
int get(int n)
{
        int k = 0;
        while (n)
        {
                n/=10;
                k++;
        }
        return k;
}
//是否为质数
bool iszhishu(int n)
{
        if(1==n || 2==n) return false;
        for (int m = 2;m*m<=n;m++)
        {
                if(n%m==0)
                        return false;
        }
        return true;
}
int main(void)
{
       
        for (int i = 2;i<=1000000000;i++)
        {
                if(iszhishu(i))
                {
                        if(is(i,get(i)))
                        {
                                std::cout<<i<<endl;
                        }
                }
        }
        return 0;
}

不知道对没。。

jerryxjr1220 发表于 2016-10-4 11:59:21

迷雾少年 发表于 2016-8-30 13:57
#include
#include
#include


答案应该是对的，最大的pandigital质数是7652413。
但是穷举的效率太低
我换了一种思路是直接生成pandigital然后再判断是否是质数，这样效率可以快很多。
7652413


'''求最大的pandigital质数'''
def isPrime(num):
        if num == 2:
                return True
        elif num%2 == 0:
                return False
        else:
                for i in range(3,int(num**0.5+1),2):
                        if num%i == 0:
                                return False
                return True

def getPan(n):
        if n == 2:
                return
        if n>2:
                pan = getPan(n-1)
                length = len(str(pan))
                pannew = []
                for each in pan:
                        pannew.append(int(str(n)+str(each)))
                        pannew.append(int(str(each)+str(n)))
                        for j in range(1,length):
                                pannew.append(int(str(each)[:j]+str(n)+str(each)))
                return pannew

masterlist = []
for k in range(9,6,-1):
        testpan = getPan(k)
        for eachpan in testpan:
                if isPrime(eachpan):
                        masterlist.append(eachpan)
print (max(masterlist))

jerryxjr1220 发表于 2016-10-17 01:05:07

芒果加黄桃 发表于 2017-1-15 11:07:03

# encoding:utf-8
# 寻找周长1000以下，能够成直角三角形最多的数
from time import time
from math import sqrt
from itertools import permutations
def getPrimes(N=50000):
    l_result = * N
    l_result, l_result = False, False
    for i in range(0, N):
      if l_result:
            for j in range(i * i, N, i):
                l_result = False
    return
def isPrime(N, l_primes):
    t = int(sqrt(N)) + 1
    for i in l_primes:
      if i > t:
            return True
      if N % i == 0:
            return False
    return True
def euler041():
    l_primes = getPrimes()
    l_result = []
    l_tmp =
    for k in range(2, 10):
      l_tmp.append(k)
      l_nums = permutations(l_tmp, k)
      for each in l_nums:
            s = ''
            for i in list(each):
                s += str(i)
            if isPrime(int(s), l_primes):
                l_result.append(int(s))
    print(l_result)
if __name__ == '__main__':
    start = time()
    euler041()
    print('cost %.6f sec' % (time() - start))


cost 1.680193 sec

芒果加黄桃 发表于 2017-1-15 11:09:37

jerryxjr1220 发表于 2016-10-17 01:05


怎么学习一下隐藏内容啊{:5_91:}

渡风 发表于 2017-6-12 21:40:35

本帖最后由 渡风 于 2017-6-12 22:14 编辑

此代码使用matlab编程
Problem41所用时间为26.4828秒
Problem41的答案为7652413
思路跟楼上基本一致，先找出pandigital 数，然后重排。matlab 效率较慢
%% Problem41.m
%最后编辑时间：2017-06-12 21:37 版本1.0
%找出最大的n为的pandigital数
function Output = Problem41()
tic
AllNum = '123456789';
Output = 0;
flag = 0; %为跳出第二层循环做准备
for ii = 9: -1 :6
    Numstr = perms(AllNum(1:ii));   %得到全排列数
    Pandigital = sort(Numstr,3);    %全排列重排
    = size(Pandigital);
    for jj = 1:M
      if Isprime(str2double(Pandigital(jj,:))) == 1
            Output = Pandigital(jj,:);
            flag = 1;
            break
      end
    end
    if flag == 1
      break
    end
end
      
toc

disp('此代码使用matlab编程')
disp(['Problem41所用时间为',num2str(toc),'秒'])
disp(['Problem41的答案为',Output])
end
%% 判断一个数是否为质数
% 最后编辑时间：17-06-12 21:42 版本：1.0
function Output = Isprime(n)
if n == 2
    Output = ture;
else
    if mod(n,2) == 0
      Output = false;
    else
      Output = true;
      for ii = 3: 2 : floor(sqrt(n))
            if mod(n, ii) == 0
                Output= false;
                break
            end
      end
    end
end
end

zengtaozt 发表于 2017-8-19 17:18:11

from itertools import permutations
from time import time
start = time()


def judgePrime(n):
    if n == 1:
      return False
    for i in range(3, int(n ** 0.5) + 1,2):
      if n % i == 0 and n != 2:
            return False
    return True

list_1=[]
for i in permutations('7654321'):
      if int(''.join(i))%2 ==0:
          continue
      if judgePrime(int(''.join(i))):
          list_1.append(int(''.join(i)))

print(max(list_1))

print("Program running cost %.6f secs!" % (time() - start))

7652413
Program running cost 0.092005 secs!

ciamisix 发表于 2018-7-14 15:08:39

本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:39 编辑

由题可知9，8位数都不可能，
9+8+7+6+5+4+3+2+1=45被3整除
8+7+6+5+4+3+2+1=36   被3整除
因此最大可能是7位数
判断是否是质数的就不写了
C语言写的

int main()
{
    __int64 i,j;      
    for (i = 7654321;i > 1000001;i -= 2)
    {

      if (isPrime(i))
      {
            int a = { 1,0,0,0,0,0,0,0,1,1 };
            int flag = 1;
            j = i;
            while (j)
            {
                if (a == 1)
                {
                  flag = 0;
                  break;
                }

                else
                  a = 1;
                j /= 10;
            }            
            if (flag == 1)
            {
                printf("%lld\n", i);
                break;
            }
      }
    }   
    return 0;
}

JAY饭 发表于 2018-11-8 04:44:36

import itertools
import math
from time import time

def prime():
   
    lst1,flag = ,True
    for i in range(5,int(math.sqrt(987654321))+1,2):
      flag = True
      for j in lst1:
            if i%j == 0:
                flag = False
                break
      if flag: lst1.append(i)
    return lst1
            
def welcomebeijing(num,primelist):
    for i in primelist:
      if num%i == 0: return False
      elif i*i > num:
            return True


def yie(lst):
   
    primelist = prime()
   
    for k in range(9,3,-1):
      for i in itertools.permutations(lst,k):
            m = ''
            for j in i:
                m += str(j)
            
            m = int(m)
            if welcomebeijing(m,primelist):
                print(m)
                return
      lst.pop(0)

s = time()
lst =
yie(lst)
t = time()-s
print('cost%.2fs'%t)

k往事如烟k 发表于 2019-3-29 13:55:47

本帖最后由 k往事如烟k 于 2019-3-29 13:57 编辑


def isPrime(num):
    if num <= 1:
      return False
    else:
      for i in range(2, int(num**0.5+1)):
            if num % i == 0:
                return False
      else:
            return True

def isPandigital(num):
    if len(str(num)) > 9:
      return False
    else:
      numTempList = []
      refNumList = []
      for i in range(len(str(num))):
            numTempList.append(int(str(num)))
            refNumList.append(i+1)
      numList = list(set(numTempList))
      if numList == refNumList:
            return True
      else:
            return False

#一个n位数的不重复数字的全排列
def perm(n):
    if n < 1 or n > 9:
      return "输入有误，n应为1~9之间的整数！"
    else:
      import itertools

      for i in range(1, n+1):
            if i == 1:
                listTemp =
            else:
                listTemp = []
                for j in range(1, i+1):
                  listTemp.append(j)

      list1 = list(itertools.permutations(listTemp, len(listTemp)))
      numList = []
      for i in range(len(list1)):
            numStr = ""
            for j in range(len(list1)):
                numStr += str(list1)
            num = int(numStr)
            numList.append(num)
      return numList

allNumList = []
for n in range(1, 10):
    for each in perm(n):
      allNumList.append(each)

PrimePandigitalNumList = []
for each in allNumList:
    if isPrime(each) and isPandigital(each):
      PrimePandigitalNumList.append(each)

PrimePandigitalNumList.sort()
print(PrimePandigitalNumList[-1])
7652413

王小召 发表于 2019-6-14 14:09:58

本帖最后由 王小召 于 2019-6-14 14:12 编辑

最大值：7652413
用时：0.4368028 秒


import itertools
import math
import time

def is_prime(num):
    if num == 2 or num == 3:
      return True
    elif num == 1 or not num % 2 or not num % 3:
      return False
    else:
      for i in range(3, int(math.sqrt(num)) + 1):
            if not num % i:
                return False
      return True

def cal_result():
    result = []
    for num in range(10, 3, -1):
      for each in itertools.permutations():
            if is_prime(int("".join(each))):
                result.append(int("".join(each)))
      if result:
            return result

print("最大值：{}\n用时：{} 秒".format(max(cal_result()), time.process_time()))

永恒的蓝色梦想 发表于 2019-7-21 16:00:37

本帖最后由 永恒的蓝色梦想 于 2019-8-5 12:13 编辑

根据题意，我们可以知道2,3,5,6,8,9位的都可以被3整除，所以只有可能是7,4,1位的。
从后向前算效率较高，先试了7位的，idle中直接跑出来。
>>> from itertools import permutations
>>> def ip(x):
    if x%2==0 or(x%6!=1 and x%6!=5):return False
    for i in range(3,int(x**0.5+1),2):
      if x%i==0:return False
    return True

>>> s=permutations('7654321')
>>> for i in s:
        i=int(''.join(i))
        if ip(i):
                print(i)
                break

7652413

a1351468657 发表于 2021-3-19 21:11:25

#include <stdio.h>
#include <string.h>
#include <math.h>

int check_prime(int);
int check_num(int);

int check_prime(int num)
{
       
        int i, j;
        j = sqrt(num + 1);
        for (i = 2; i <= j; i++)
        {
                if (num % i == 0)
                {
                        return 0;
                }
        }
        return 1;
}
int check_num(int num)
{
        int j, k, a = { 0 };
        k = num;
        while (k)
        {
                j = k % 10;
                if (a)
                {
                        return 0;
                }
                a = 1;
                k /= 10;
        }
        return 1;
}

main()
{
        char str;
        int i, j;
        for (i = 7654321; i > 0; i -= 2)
        {
                sprintf(str, "%d", i);
                for (j = 0; j < strlen(str); j++)
                {
                        if (str > '7')
                        {
                                goto Label;
                        }
                }       
                if (check_num(i))
                {
                        if (check_prime(i))
                        {
                                printf("%d\n", i);
                                break;
                        }
                }
        Label:continue;
        }
}

7652413

ft215378 发表于 2021-10-21 16:03:12

#最大的n位pandigital质数
from time import *
from math import *
from itertools import *
#判断是否是素数
def is_prime(number):
    if number > 1:
      if number == 2:
            return True
      if number % 2 == 0:
            return False
      for a in range(3,int(sqrt(number) + 1),2):
            if number % a == 0:
                return False
      return True
    return False

#输出n位pandigital质数列表
def prime_pandigital(n):
    num_str = ''
    for i in range(1, n+1):
      num_str += str(i)
    a = permutations(num_str, n)
    num_list = []
    for each in a:
      num_list.append(each)
    num = ''
    res = []
    for each in num_list:
      for i in each:
            num += i
      if is_prime(int(num)):
            res.append(int(num))
      num = ''
    return res

start = time()
n = 2
result = 0
while n <= 9:
    if prime_pandigital(n) != []:
      result = max(prime_pandigital(n))
    n += 1
end = time()
print(result)
print("用时%2f秒" % (end-start))

guosl 发表于 2022-1-7 20:41:15

答案：7652413
耗时：0.0310001
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 10000000;
char cp;

int main(void)
{
//打造素数表
memset(cp + 2, 1, (N - 1) * sizeof(char));
for (int i = 2; i < (int)sqrt((double)N); ++i)
{
    if (cp == 0)
      continue;
    for (int j = i * i; j <= N; j += i)
      cp = 0;
}
char str = "1234567";
int nMaxPrime = 0;
for (int k = 7; k >= 1; --k)//对位数进行从大到小枚举
{
    char str1;
    strncpy_s(str1, str, k);
    str1 = 0;
    do //枚举所有的k-pandigital数
    {
      int a = atoi(str1);
      if (cp == 1)//检查是否是素数
      nMaxPrime = max(nMaxPrime, a);//保存大的
    } while (next_permutation(str1, str1 + k));
    if (nMaxPrime > 0)//找到了满足题意的数
      break;
}
cout << nMaxPrime << endl;
return 0;
}

B1tetheDust 发表于 2022-10-24 19:42:15

import time as t
import math
from itertools import permutations

start = t.perf_counter()


def check_prime(a_num):
    is_prime = True
    for i in range(2, int(math.sqrt(a_num) + 1)):
      if a_num % i == 0:
            is_prime = False
    return is_prime


num_list = list(permutations('1234567'))
length_list = len(num_list)
for j in range(length_list):
    num_str = ''
    for k in num_list[- j - 1]:
      num_str += k
    num = int(num_str)
    if check_prime(num):
      break

print(num)
print("It costs %f s" % (t.perf_counter() - start))



7652413
It costs 0.002284 s

查看完整版本: 题目41：最大的n位pandigital质数是多少？