Problem 41(Pandigital prime)

Problem 41(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?

 

In Python:

import math
import time

def isprime(n):
    if n == 0 or n == 1:
        return False
    else:
        for i in range(2, n):
            if n % i == 0:
                return False
        return True

def swap(s, i, j):
    nList = list(s)
    nList[j], nList[i] = nList[i], nList[j]
    return ''.join(nList)

def undersort(s, i):
    nList = list(s)
    nList = nList[0: i] + sorted(nList[i:])
    return ''.join(nList)

def lexico(nStr):
    lenStr = len(nStr)
    for i in range(lenStr - 2, -1, -1):
        for j in range(lenStr - 1, i, -1):
            if int(nStr[i]) < int(nStr[j]):
                nStr = swap(nStr, i, j)
                nStr = undersort(nStr, i + 1)
                return nStr

startTime = time.time()
nStr = '1234567'
cStr = math.factorial(len(nStr))
panList = [1234567]
for i in range(1, cStr):
    nStr = lexico(nStr)
    panList.append(int(nStr))
for i in range(cStr, 1, -1):
    if isprime(panList[i - 1]):
            print(panList[i - 1])
            break
print(time.time() - startTime, "seconds")

Run time: 0.7171950340270996 seconds

 

In Java:

package project_euler41_50;

import java.util.ArrayList;
import java.util.Collections;

public class Euler41 {
	public static Boolean isprime(int n) {
		if (n == 0 || n == 1) {
			return false;
		} else {
			for (int i = 2; i < n; i++) {
				if (n % i == 0) {
					return false;
				}
			}
			return true;
		}
		
	}
	public static int factorial(int n) {
		if (n == 1) {
			return 1;
		}
		return n * factorial(n - 1);
	}
	public static String swap(String s, int i, int j) {
		int temp;
		String nstr="";
		String nData[];
		ArrayList<Integer> nList = new ArrayList<Integer>();
		nData = s.split("");
		for (int k = 0; k < nData.length; k++) {
			nList.add(Integer.parseInt(nData[k]));
		}
		temp = nList.get(i);
		nList.set(i, nList.get(j));
		nList.set(j, temp);
		for (int num : nList) {
			nstr += Integer.toString(num);
		}
		return nstr;
	}
	public static String undersort(String s, int i) {
		String nstr = "";
		String nData[];
		ArrayList<Integer> nList1 = new ArrayList<Integer>();
		ArrayList<Integer> nList2 = new ArrayList<Integer>();
		nData = s.split("");
		for (int k = 0; k < i; k++) {
			nList1.add(Integer.parseInt(nData[k]));
		}
		for (int k = i; k < nData.length; k++) {
			nList2.add(Integer.parseInt(nData[k]));
		}
		Collections.sort(nList2);
		nList1.addAll(nList2);
		for (int num : nList1) {
			nstr += Integer.toString(num);
		}
		return nstr;
	}
	public static String lexico(String s) {
		int check = 0;
		int lenStr = s.length();
		String nStr = "";
		String nData[];
		ArrayList<Integer> nList = new ArrayList<Integer>();
		nData = s.split("");
		for (int k = 0; k < nData.length; k++) {
			nList.add(Integer.parseInt(nData[k]));
		}
		for (int i = lenStr - 2; i > -1; i--) {
			for (int j = lenStr - 1; j > i; j--) {
				if (nList.get(i) < nList.get(j)) {
					nStr = swap(s, i, j);
					nStr = undersort(nStr, i + 1);
					check = 1;
					break;
				}
			}
			if (check == 1) {
				break;
				
			}
		}
		return nStr;
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		String nStr = "1234567";
		int cStr = factorial(nStr.length());
		ArrayList<Integer> panList = new ArrayList<Integer>();
		panList.add(1234567);
		for (int i = 1; i < cStr; i++) {
			nStr = lexico(nStr);
			panList.add(Integer.parseInt(nStr));
		}
		for (int i = cStr; i > 1; i--) {
			if (isprime(panList.get(i - 1))) {
				System.out.println(panList.get(i - 1));
				break;
			}
		}
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.253seconds

 

Solution: 7652413