Estoy tratando de resolver Problem 41 del proyecto Euler en Java, al contar el número de 99888888 a 80000000 (que tomó mucho tiempo :(), recibí 98765431 como respuesta, pero estoy obteniendo esa respuesta incorrecta. ¿Alguien podría decirme por qué no obtuve la respuesta correcta y cómo puedo acelerar mi programa?Consejos para resolver el problema # 41 del proyecto euler
Un número pandigital no necesita contener todos los números de 1 to 9, pero todo desde 1 to length.
Por lo tanto, deberás probar todas las permutaciones desde 1 to 9 comenzando con 1 dígito y subiendo, filtrando todos los números primos y, luego, tomando la más grande.
Esto se siente como el camino a seguir. Solo hay 362880 permutaciones de 9 elementos, por lo que se puede calcular en un tiempo razonable. – Buhb
No realmente: 362880 + 40320 + 5040 + 720 + 120 + 24 + 6 + 2 = 409112 permutaciones (recuerde agregar permutaciones con 8, 7, 6 dígitos, etc.), que contengan 538 primos dentro de él –
Hecho: Si la suma de los 10 dígitos base de un entero es 0 mod 3, ese entero es divisible por 3. Por lo tanto, cada número de 9 dígitos y 8 dígitos es divisible por 3 y no puede ser un primo. –
Las únicas posibles números primos son aquellos Pandigital con la longitud 1, 4, 7 & porque cada otro número Pandigital tiene la suma de sus dígitos divisible por 3.
Por lo tanto, sólo se necesitaría para poner a prueba para 7! = 5040 permutaciones.
Tendrás que explicarlo con más profundidad, me temo, ¿a qué te refieres con los únicos números pandigitales principales posibles son 1, 4 y 7? Por un lado, 4 no es primo. – andrewsi
Aquí es el enunciado del problema:
Diremos que un número de n dígitos es Pandigital si se hace uso de todos los dígitos 1 a N exactamente una vez. Por ejemplo, 2143 es un pandigital de 4 dígitos y también es primo. ¿Cuál es el primado pandigital más grande que existe?
Escribí un programa que comenzó con 987654321 y contó abajo. Verifiqué que el número era pandigital, y si lo era, comprobé si era primo.
Tardó 66 segundos en mi computadora con Windows 8.1 para encontrar el pandigital principal más grande.
Cuando probé al revés, primero primero, luego pandigital, el programa tomó más de 66 segundos. Lo cancelé
Cuando apliqué la sugerencia de GregS sobre el descuento de todos los números pagigitales de 9 y 8 dígitos, y comencé a contar desde 7654321, mi algoritmo de fuerza bruta tardó 13 milisegundos.
Para obtener una solución en un tiempo "razonable", necesita las siguientes observaciones basadas en la propiedad especial que un número es divisible por 3 si la suma de sus dígitos es divisible por 3:
divisible by
1+2+3+4 = 10 -
1+2+3+4+5 = 15 3
1+2+3+4+5+6 = 21 3
1+2+3+4+5+6+7 = 28 -
1+2+3+4+5+6+7+8 = 36 3
1+2+3+4+5+6+7+8+9 = 45 3
Entonces, un número pandigital "grande" grande tiene 4 o 7 dígitos. (un número primo mayor que 3 no es divisible por 3)
Como desea obtener el número más grande, es mejor comenzar con los números de 7 dígitos y continuar verificando los números de 4 dígitos solo si el número era extraviado. Por supuesto, existe un número de 4 dígitos, porque está especificado: 2143.
Ahora, una posible solución es similar a esto:
public class P41 {
public static void main(String[] args) {
boolean wasFound = false;
for (int nr = 7654321; nr >= 1234567; nr -= 2) { // even != prime
if (isPandigital(nr) && isOddPrime(nr)) {
System.out.println(nr);
wasFound = true;
break;
}
}
if (!wasFound) {
/* not <=, because 1234 is even */
for (int nr = 4321; nr > 1234; nr -= 2) {
if (isPandigital(nr) && isOddPrime(nr)) {
System.out.println(nr);
break;
}
}
}
}
private static boolean isOddPrime(int x) {
int sqrt = (int) Math.sqrt(x);
for (int i = 3; i <= sqrt; i += 2) {
if (x % i == 0) {
return false;
}
}
return true;
}
private static int getNumberOfDigits(int x) {
int count = 0;
while (x > 0) {
count++;
x /= 10;
}
return count;
}
private static boolean isPandigital(int x) {
int numberOfDigits = getNumberOfDigits(x);
Set<Integer> digits = new HashSet<Integer>();
for (int i = 1; i <= numberOfDigits; i++) {
digits.add(i);
}
for (int i = 1; i <= numberOfDigits; i++) {
digits.remove(x % 10);
x /= 10;
}
if (digits.size() == 0) {
return true;
} else {
return false;
}
}
}
Tiempo: 8 ms .
'98765431' no es un número primo pandigital, ya que no contiene' 2' –
Mirando la descripción del problema, nunca mencionan que la respuesta debe ser la base 10.Esto parece un poco descuidado, como conjeturo que existen primos pandigitales arbitrariamente grandes si eliges tu base de manera apropiada. – Benno