We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
1) Create all permutation of numbers: (1,2,3) => 123, 132, 213,... Then we have a list of m = 1! + 2! +...+ 9! = 409113 numbers (O(m))
2) For every element in the list we'll check if it's prime or not, then put it in a primes list (O(m^1.5)
3) Sort this primes list (O(mlogm))
4) Use Binary Search Tree to find the closest prime to n (O(logm))
fromitertoolsimportpermutationsfrombisectimportbisect_left# Function to determine a prime number # Time complexity = O(sqrt(n))defisPrime(n):ifn==2orn==3:returnTrueifn%2==0orn<2:returnFalseforiinrange(3,int(n**0.5)+1,2):#Onlyoddnumbersifn%i==0:returnFalsereturnTruedefPandigital_Prime():# Create all permutation of numbers# Time complexity = O(m) = O(1! + 2! +...+ 9! = 409113)permTuples=[]foriinrange(2,10):perm=list(permutations(range(1,i+1)))permTuples+=perm# Convert tuples to integer# Time complexity = O(m)permNums=[]foriinpermTuples:num=int(''.join([str(j)forjini]))permNums.append(num)# For every element in the list we'll check if it's prime or not# Time complexity = O(m^1.5)primes=[]foriinpermNums:ifisPrime(i)==True:primes.append(i)# Sort the list for better access of index # Time complexity = O(mlogm)primes.sort()returnprimesif__name__=='__main__':primes=Pandigital_Prime()for_inrange(int(input())):n=int(input())# Use Binary Search Tree to find the closest prime to n# Time complexity = O(logm)idx=bisect_left(primes,n)ifidx<len(primes)andprimes[idx]<=n:print(primes[idx])elifprimes[idx-1]<=n:print(primes[idx-1])else:print(-1)
Project Euler #41: Pandigital prime
You are viewing a single comment's thread. Return to all comments →
Hints for everyone:
1) Create all permutation of numbers: (1,2,3) => 123, 132, 213,... Then we have a list of m = 1! + 2! +...+ 9! = 409113 numbers (O(m))
2) For every element in the list we'll check if it's prime or not, then put it in a primes list (O(m^1.5)
3) Sort this primes list (O(mlogm))
4) Use Binary Search Tree to find the closest prime to n (O(logm))