Comment trouver le plus grand facteur premier 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); } } } } 

Le code ci-dessus fonctionne pour n = 6008514751 . Cependant, cela ne fonctionne pas pour n = 600851475143 , même si ce nombre est toujours dans la plage d’un long .
Que puis-je faire pour que cela fonctionne?

Un problème potentiel est que i et j sont int et risquent de déborder pour n grand (en supposant que int soit plus étroit que long , ce qui est souvent le cas).

Un autre problème est que pour n = 600 851 475 143, votre programme fait beaucoup de travail (le facteur le plus important est 6857). Il n’est pas déraisonnable de s’attendre à ce que cela prenne beaucoup de temps.

Utilisez long s à la place de int s. Mieux encore, utilisez uint64_t qui a été défini depuis C99 (acquittez Zaibis). C’est un type intégral non signé de 64 bits sur toutes les plateformes. (Le code tel que vous l’avez débordera sur certaines plates-formes).

Et nous devons maintenant faire fonctionner votre algorithme plus rapidement:

Votre test de prime est inefficace; vous n’avez pas besoin de parcourir tous les nombres pairs. Il suffit de parcourir les nombres premiers; jusqu’à et égal à la racine carrée du nombre que vous testez (et non à mi-chemin comme vous le faites actuellement).

Où trouvez-vous les primes? Appelez votre fonction récursivement. Bien qu’en réalité, je serais tenté de cacher les nombres premiers jusqu’à, par exemple, 65 536.

De l’ISO / CEI 9899: TC3

5.2.4.2.1 Tailles des types entiers

[…]

Leurs valeurs définies par la mise en œuvre doivent être égales ou supérieures en magnitude (valeur absolue) à celles indiquées, avec le même signe.

[…]

– valeur minimale pour un object de type long int

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

– valeur maximale pour un object de type long int

LONG_MAX +2147483647 // 2 ^ 31 – 1

MODIFIER:

Désolé j’ai oublié d’append ce que cela devrait vous dire.

Le point est long, il n’est même pas nécessaire de pouvoir conserver la valeur que vous avez mentionnée, car la norme stipule qu’elle doit pouvoir contenir au moins 4 octets avec un signe afin que votre ordinateur puisse simplement contenir des valeurs. jusqu’à 2147483647 dans une variable de type long .

Sur une machine 32 bits long plage va de -2,147,483,648 2,147,483,647 à 2,147,483,647 et sur une machine 64 bits, elle est comprise entre -9,223,372,036,854,775,808 9,223,372,036,854,775,807 -9,223,372,036,854,775,808 et 9,223,372,036,854,775,807 ( NOTE : cette 9,223,372,036,854,775,807 n’est pas prescrite par C et peut varier d’un compilateur à un autre).
Comme OP a déclaré dans un commentaire qu’il est sur 32 bits, 600851475143 va hors de scope car il ne correspond pas à la plage de long .

Essayez de changer n en long long int .. et de changer i, j en long

EDIT: définir n comme ceci:

 long long int n = 600851475143LL; 

LL – est un suffixe pour imposer le type long long …