¿Cómo encontrar el factor primo más grande de 600851475143?

#include  main() { long n=600851475143; int i,j,flag; for(i=2;i<=n/2;i++) { flag=1; if(n%i==0)//finds factors backwards { for(j=2;j<=(n/i)/2;j++)//checks if factor is prime { if((n/i)%j==0) flag=0; } if(flag==1) { printf("%d\n",n/i);//displays largest prime factor and exits exit(0); } } } } 

El código anterior funciona para n = 6008514751 . Sin embargo, no funciona para n = 600851475143 , aunque ese número todavía está dentro del rango de un long .
¿Qué puedo hacer para que funcione?

Un problema potencial es que i y j son int , y podrían desbordarse para n grande (suponiendo que int sea ​​más estrecho que long , lo que a menudo es).

Otro problema es que para n = 600,851,475,143 su progtwig hace bastante trabajo (el factor más importante es 6857). No es irrazonable esperar que tarde mucho en completarse.

Use s long en lugar de int s. Mejor aún, use uint64_t que se ha definido desde C99 (acuse de recibo de Zaibis). Es un tipo integral sin signo de 64 bits en todas las plataformas. (El código que tengas se desbordará en algunas plataformas).

Y ahora necesitamos que su algoritmo funcione más rápido:

Su prueba para prime es ineficiente; No necesitas iterar sobre todos los números pares. Sólo iterar sobre primos; hasta e igual a la raíz cuadrada del número que estás probando (no a la mitad de lo que haces actualmente).

¿De dónde sacas los números primos? Bueno, llama a tu función recursivamente. Aunque en realidad estaría tentado a almacenar los números primos hasta, por ejemplo, 65536.

Desde ISO / IEC 9899: TC3

5.2.4.2.1 Tamaños de tipos enteros

[…]

Sus valores definidos por la implementación serán iguales o mayores en magnitud (valor absoluto) a los mostrados, con el mismo signo.

[…]

– Valor mínimo para un objeto de tipo long int.

LONG_MIN -2147483647 // – (2 ^ 31 – 1)

– valor máximo para un objeto de tipo long int

LONG_MAX +2147483647 // 2 ^ 31 – 1

EDITAR:

Lo siento, me olvidé de agregar lo que esto debería decirle.

El punto es largo, ni siquiera tiene que ser capaz de mantener el valor que mencionó, ya que el estándar dice que tiene que ser capaz de mantener al menos 4 bytes con signo para que sea posible que su máquina solo pueda mantener valores Hasta 2147483647 en una variable de tipo long .

En la máquina de 32 bits de long scope de -2,147,483,648 a 2,147,483,647 y en la máquina de 64 bits su rango es de -9,223,372,036,854,775,808 a 9,223,372,036,854,775,807 ( NOTA : Esto no es obligatorio según el estándar C y puede variar de un comstackdor a otro).
Como OP dijo en un comentario que está en 32 bits, 600851475143 se sale del rango, ya que no encaja en el rango de long .

Intente cambiar n a long long int .. y cambie i, j a long

EDITAR: definir n como este:

 long long int n = 600851475143LL; 

LL – es un sufijo para imponer el tipo largo y largo …