sol1.py

"""
Pandigital prime
Problem 41: https://projecteuler.net/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?

All pandigital numbers except for 1, 4 ,7 pandigital numbers are divisible by 3.
So we will check only 7 digit pandigital numbers to obtain the largest possible
pandigital prime.
"""

from __future__ importannotations

importmath
fromitertoolsimportpermutations


defis_prime(number: int) ->bool:
"""Checks to see if a number is a prime in O(sqrt(n)).

 A number is prime if it has exactly two factors: 1 and itself.

 >>> is_prime(0)
 False
 >>> is_prime(1)
 False
 >>> is_prime(2)
 True
 >>> is_prime(3)
 True
 >>> is_prime(27)
 False
 >>> is_prime(87)
 False
 >>> is_prime(563)
 True
 >>> is_prime(2999)
 True
 >>> is_prime(67483)
 False
 """

if1<number<4:
# 2 and 3 are primes
returnTrue
elifnumber<2ornumber%2==0ornumber%3==0:
# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
returnFalse

# All primes number are in format of 6k +/- 1
foriinrange(5, int(math.sqrt(number) +1), 6):
ifnumber%i==0ornumber% (i+2) ==0:
returnFalse
returnTrue


defsolution(n: int=7) ->int:
"""
 Returns the maximum pandigital prime number of length n.
 If there are none, then it will return 0.
 >>> solution(2)
 0
 >>> solution(4)
 4231
 >>> solution(7)
 7652413
 """
pandigital_str="".join(str(i) foriinrange(1, n+1))
perm_list= [int("".join(i)) foriinpermutations(pandigital_str, n)]
pandigitals= [numfornuminperm_listifis_prime(num)]
returnmax(pandigitals) ifpandigitalselse0


if__name__=="__main__":
print(f"{solution() =}")