TheAlgorithms-Python
77 строк · 2.0 Кб
1"""
2Pandigital prime
3Problem 41: https://projecteuler.net/problem=41
4
5We shall say that an n-digit number is pandigital if it makes use of all the digits
61 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
7What is the largest n-digit pandigital prime that exists?
8
9All pandigital numbers except for 1, 4 ,7 pandigital numbers are divisible by 3.
10So we will check only 7 digit pandigital numbers to obtain the largest possible
11pandigital prime.
12"""
13
14from __future__ import annotations15
16import math17from itertools import permutations18
19
20def is_prime(number: int) -> bool:21"""Checks to see if a number is a prime in O(sqrt(n)).22
23A number is prime if it has exactly two factors: 1 and itself.
24
25>>> is_prime(0)
26False
27>>> is_prime(1)
28False
29>>> is_prime(2)
30True
31>>> is_prime(3)
32True
33>>> is_prime(27)
34False
35>>> is_prime(87)
36False
37>>> is_prime(563)
38True
39>>> is_prime(2999)
40True
41>>> is_prime(67483)
42False
43"""
44
45if 1 < number < 4:46# 2 and 3 are primes47return True48elif number < 2 or number % 2 == 0 or number % 3 == 0:49# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes50return False51
52# All primes number are in format of 6k +/- 153for i in range(5, int(math.sqrt(number) + 1), 6):54if number % i == 0 or number % (i + 2) == 0:55return False56return True57
58
59def solution(n: int = 7) -> int:60"""61Returns the maximum pandigital prime number of length n.
62If there are none, then it will return 0.
63>>> solution(2)
640
65>>> solution(4)
664231
67>>> solution(7)
687652413
69"""
70pandigital_str = "".join(str(i) for i in range(1, n + 1))71perm_list = [int("".join(i)) for i in permutations(pandigital_str, n)]72pandigitals = [num for num in perm_list if is_prime(num)]73return max(pandigitals) if pandigitals else 074
75
76if __name__ == "__main__":77print(f"{solution() = }")78