Encuentra el mayor factor de número primo?

Necesito encontrar Los factores primos de 13195 son 5, 7, 13 y 29. / * El más grande es 377. * / ¿Cuál es el factor primo más grande del número 600851475143?

#include int main() { int i, j = 0; /*Code works really fine for 13195 or 26*/ long value, large = 600851475143 /*13195*/; for(value = (large - 1) ; value >= 3; value--) { if(large % value == 0) { /*printf("I am here \n");*/ if((value % 2 != 0) && (value % 3 != 0) && (value % 5 != 0) && (value % 7 != 0) ) { j = 1; break; } } } if (j == 1) { printf("%ld", value); } return 0; } 

¿A dónde va mal?

 #include //Euler problem #3 int main(){ long long i, sqi; long long value, large = 600851475143LL; long long max = 0LL; i = 2LL; sqi = 4LL; //i*i for(value = large; sqi <= value ; sqi += 2LL * i++ + 1LL){ while(value % i == 0LL){ value /= (max=i); } } if(value != 1LL && value != large){ max = value; } if(max == 0LL){ max = large; } printf("%lld\n", max); return 0; } 
  1. 600851475143 es demasiado grande para caber en un entero de 32 bits. long puede ser de 32 bits en su máquina. Es necesario utilizar el tipo de 64 bits. El tipo de datos exacto dependerá de su plataforma, comstackdor.

  2. Su código de comprobación principal es incorrecto. Usted está asumiendo que si algo no se divide en 2, 3, 5, 7, entonces eso es primo.

Lo más importante que está mal aquí es que su código es demasiado lento: incluso si soluciona otros problemas, como usar un tipo de datos incorrecto para sus enteros y probar algunos divisores que definitivamente no son primos, iterando de uno en uno desde 10 ^ 11 simplemente no terminará en la vida de su computadora es un gran desperdicio.

Le recomiendo que lea el ejemplo en la página 35 de este libro clásico , donde Dijkstra lo guía en el proceso de escritura de un progtwig que imprime los primeros 1000 números primos. Este ejemplo debería proporcionarle suficiente intuición matemática para acelerar sus propios cálculos, incluida la parte en la que comienza la búsqueda desde la raíz cuadrada del número que está intentando factorizar.

600851475143 probablemente esté por encima de la precisión del tipo de datos long de su plataforma. Requiere al menos 40 bits para almacenar. Puedes usar esto para calcular cuántos bits tienes:

 #include  printf("my compiler uses %u bits for the long data type\n", (unsigned int) (CHAR_BIT * sizeof (long))); 

Debe agregar una L como sufijo a un número que desborda MAX INT, por lo que esta línea:

 long value, large = 600851475143; 

Debiera ser:

 long value, large = 600851475143L; // ^ 

Para hacer esto, debe establecer que el valor es primo, es decir, que no tiene factores primos.

Ahora, su pequeña pieza de código 3/5/7 simplemente no es lo suficientemente buena; debe verificar si el valor tiene CUALQUIER factor primo más bajo (por ejemplo, 11/13/17).

Desde una perspectiva estratégica, si desea utilizar este análisis, debe verificar una lista de todos los factores primos que ha encontrado hasta ahora y verificarlos mientras compara con los primeros 3 números primos.

Un método más fácil (pero menos eficiente) sería escribir un IsPrimeFunction () y verificar la primalidad de cada divisor y almacenar el más grande.

 public class LargeFactor{ public static void main(String []args){ long num = 600851475143L; long largestFact = 0; long[] factors = new long[2]; for (long i = 2; i * i < num; i++) { if (num % i == 0) { // It is a divisor factors[0] = i; factors[1] = num / i; for (int k = 0; k < 2; k++) { boolean isPrime = true; for (long j = 2; j * j < factors[k]; j++) { if (factors[k] % j == 0) { isPrime = false; break; } } if (isPrime && factors[k] > largestFact) { largestFact = factors[k]; } } } } System.out.println(largestFact); } } 

El código anterior utiliza el hecho de que solo necesitamos verificar todos los números hasta la raíz cuadrada cuando buscamos factores.