Trouvez le plus grand facteur nombre premier?

Question

Je dois trouver Les facteurs premiers de 13195 sont 5, 7, 13 et 29. /* Le plus grand est 377. */ Quel est le plus grand facteur premier du nombre 600851475143?

#include<stdio.h> 
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; 
} 

Où cela ne va pas?

Answer 1

#include<stdio.h> 
//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; 
} 

Answer 2

600851475143 est probablement supérieure à la précision du type de données long de votre plateforme. Il faut au moins 40 bits pour stocker. Vous pouvez l'utiliser pour savoir combien de bits vous avez:

#include <limits.h> 

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

Answer 3

Vous devez ajouter un L comme suffixe à un nombre qui déborde MAX INT, donc cette ligne:

long value, large = 600851475143; 

devrait être:

long value, large = 600851475143L; 
//       ^

Answer 4

pour ce faire, vous devez établir que la valeur est le premier - à savoir ce qui est n'a pas de facteurs premiers.

Maintenant, votre petit morceau de code de vérification 3/5/7 n'est tout simplement pas assez bon - vous devez vérifier que la valeur a des facteurs premiers inférieurs (par exemple 11/13/17). D'un point de vue stratégique, si vous voulez utiliser cette analyse, vous devez vérifier la liste de tous les facteurs premiers que vous avez trouvés jusqu'à présent et vérifier par rapport aux trois premiers nombres premiers.

Une méthode plus simple (mais moins efficace) consisterait à écrire un IsPrimeFunction() et vérifier la primalité de chaque diviseur et stocker le plus grand.

Answer 5

1. 600851475143 est trop grand pour tenir dans un entier de 32 bits. long peut être 32 bits sur votre ordinateur. Vous devez utiliser un type 64 bits. Le type de données exact dépendra de votre plate-forme, compilateur.

2. Votre code de vérification principal est erroné. Vous supposez que si quelque chose n'est pas divisé par 2, 3, 5, 7, alors c'est primordial.

Answer 6

La chose la plus importante qui est mal est que votre code est trop lent: même si vous résoudre d'autres problèmes, comme l'utilisation d'un mauvais type de données pour vos entiers et essayer certains diviseurs qui sont certainement pas le premier , itératif par un de 10^11 ne finira tout simplement pas dans la vie de votre ordinateur est extrêmement gaspilleur.

Je vous recommande vivement read through the example on page 35 of this classic book, où Dijkstra vous emmène à travers le processus d'écriture d'un programme d'impression des 1000 premiers nombres premiers. Cet exemple devrait vous fournir suffisamment d'intuition mathématique pour accélérer vos propres calculs, y compris la partie où vous commencez votre recherche à partir de la racine carrée du nombre que vous essayez de factoriser.

Answer 7

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); 
} 
} 

code ci-dessus utilise le fait que nous avons seulement besoin de vérifier tous les chiffres jusqu'à la racine carrée lors de la recherche des facteurs.