premier factorisation des nombres plus grands que int

Question

Ce programme fait le premier factorisation des nombres dans C.

#include <stdio.h> 

int main(void) { 
    int number, i, p, n, factors, count; 
    int numbers[1000000]; 
    int counter = 0; 
    char text[100000]; 

    for (count = 0; count < 1000000; count++) { 
     fgets(text, 10000000, stdin); 
     if (sscanf(text, "%d", &number) == 1) { 
      if (number == 0) 
       break; 
      numbers[count] = number; 
     } else { 
      numbers[count] = 0; 
     } 
    } 
    counter = 0; 
    for (i = 0; i < count; i++) { 
     if ((numbers[i] < 0) || (numbers[i] == 0)) { 
      fprintf(stderr, "Error: Wrong Input!\n"); 
      return 100; 
      break; 
     } 
     number = numbers[i]; 
     printf("Prime factorization of nubmer %d is:\n", number); 
     factors = 0; 
     for (p = 2; p * p <= number; p += 1 + (p & 1)) { 
      if (number % p == 0) { 
       n = 0; 
       factors++; 
       do { 
        number /= p; 
        n++; 
       } while (number % p == 0); 
       if (n == 1) { 
        printf("%d ", p); 
        ++counter; 
       } else 
        printf("%d^%d ", p, n); 
       ++counter; 

       if (count > 0 && number != 1) 
        printf("x "); 
      } 
     } 
     if (factors == 0 || number != 1) 
      printf("%d", number); 
     printf("\n"); 
    } 
    return 0; 
} 

Ce programme fonctionne très bien pour les nombres inférieurs à 10 . Mais ma question est, s'il y a un moyen de faire ce programme même pour des numéros comme 10 . Je sais que int ne serait pas suffisant, mais quand j'ai essayé par exemple long int, cela n'a pas fonctionné. J'ai aussi entendu quelque chose à propos de malloc, mais je continue de ne pas l'implémenter.

Answer 1

Vous pouvez utiliser long long. Mais probablement, le vrai problème est, que cela prendra un veeeeerrrryyy longtemps pour faire la factorisation sur les nombres, qui ne rentrent pas dans un int normal. Par exemple. vous essayez de factoriser un nombre premier dans la gamme 10^12, alors vous devrez faire environ 10^6 divisions. La chose au sujet de malloc ne vous aidera pas du tout à ce problème, parce que même les plus grandes valeurs prendront encore plus de temps à factoriser. Donc, si vous voulez savoir, comment fonctionne malloc, je suggère d'ouvrir une question distincte pour cela.

Answer 2

Ci-dessous est une retouche du code en utilisant unsigned long long. (J'ai jeté le fichier de choses pour garder un exemple minimal.) Si cela fonctionne pour votre but dépend de la façon dont votre système définit un long long (sur mon système, il est 64 bits). J'ai aussi refis le format de sortie pour être compatible avec la notation postfix de commande Unix dc pour que je puisse facilement vérifier si les résultats étaient corrects:

#include <stdio.h> 
#include <stdlib.h> 

int main() { 

    unsigned long long large = 18446744073709551615ULL; // 2^64 - 1 

    for (unsigned long long counter = large - 1000; counter < large; counter++) { 

     unsigned long long number = counter; 

     printf("Prime factorization of %llu is:", number); 

     unsigned long factors = 0; 

     for (unsigned long long p = 2; p * p <= number; p += 1 + (p & 1)) { 

      if (number % p == 0) { 
       factors++; 

       unsigned long n = 0; 

       do { 
        number /= p; 
        n++; 
       } while (number % p == 0); 

       if (n == 1) { 
        printf(" %llu", p); 
       } 
       else { 
        printf(" %llu %lu ^", p, n); 
       } 

       if (number != 1 && factors > 1) { 
        printf(" *"); 
       } 
      } 
     } 

     if (factors == 0 || number != 1) { 
      factors++; 

      printf(" %llu", number); 
     } 

     if (factors > 1) { 
      printf(" *"); 
     } 

     printf("\n"); 
    } 

    return 0; 
} 

EXEMPLE DE SORTIE

% ./a.out 
Prime factorization of 18446744073709550615 is: 5 563 * 751 * 8725722280871 * 
Prime factorization of 18446744073709550616 is: 2 3^3 * 41 * 7523 * 8243 * 14479 * 20879 * 
Prime factorization of 18446744073709550617 is: 79 557 * 419215600611539 * 
Prime factorization of 18446744073709550618 is: 2 2298974999 * 4011949691 * 
Prime factorization of 18446744073709550619 is: 3 3^1008659 * 677347590683 * 
Prime factorization of 18446744073709550620 is: 2 2^5 * 7 * 149 * 233 * 3795329598449 * 
Prime factorization of 18446744073709550621 is: 11 23 * 72912031911895457 * 
Prime factorization of 18446744073709550622 is: 2 3 * 479909 * 6406334004193 * 
Prime factorization of 18446744073709550623 is: 3421377637 5391612979 * 
Prime factorization of 18446744073709550624 is: 2 5^61 * 593 * 1699 * 9379762391 * 
Prime factorization of 18446744073709550625 is: 3 5 4^* 13 * 756789500459879 * 
Prime factorization of 18446744073709550626 is: 2 3743461 * 2463862195133 * 
Prime factorization of 18446744073709550627 is: 7 1283 * 4339 * 627089 * 754877 * 
Prime factorization of 18446744073709550628 is: 2 2^3 2^* 101 * 293 * 42751 * 405025111 * 
Prime factorization of 18446744073709550629 is: 17 43 * 613 * 66457 * 619442699 * 
... 

Cela est plus lent mais raisonnable . Vous pouvez pousser cet autre sur certains systèmes en échangeant unsigned long long pour une uint128_t que certains compilateurs soutiennent quelque peu: (. Et les unsigned long déclarations à unsigned long long)

typedef unsigned __int128 uint128_t; 

Vous aurez besoin de fournir des routines d'impression numérique pour le type uint128_t comme printf() ne va pas les gérer directement. J'ai essayé avec le code ci-dessus et cela a fonctionné:

Prime factorization of 340282366920938463426481119284349108124 is: 2 2^31 * 6131 * 7654271 * 21163829 * 21491837 * 128562653437 * 

% dc 
2 2^31 * 6131 * 7654271 * 21163829 * 21491837 * 128562653437 * p 
340282366920938463426481119284349108124 

Mais je ne l'ai vu terminer plus d'un numéro tout en exécutant!

Answer 3

Factoriser de grands nombres nécessite généralement une approche plus subtile que la simple division d'essai. Voici une méthode de contour possible:

1. Faites une liste de tous les nombres premiers jusqu'à, disons, 25 000. Utilisez la liste pour supprimer tous les facteurs premiers inférieurs à 25 000.
2. S'il reste> 1, vérifier si le reste est premier avec un test de Miller-Rabin ou similaire.
3. Si le reste est premier, alors vous avez trouvé le dernier facteur.
4. Si le reste n'est pas premier, alors vous allez devoir le factoriser. Cela sera inévitablement lent, j'en ai peur.

Answer 4

utilisant le type unsigned long long pour number et les principaux facteurs vous amène à 10 au prix de plus des temps de calcul. Notez toutefois que la définition d'une grande baie locale avec stockage automatique peut poser des problèmes, notamment lorsqu'elle atteint une taille de 8 mégaoctets, comme ce serait le cas pour le type unsigned long long (ce type est au moins de 64 bits). L'attribuer à partir du tas est plus sûr.

Voici une version adaptée du code:

#include <stdio.h> 
#include <stdlib.h> 

#define NUMBER_MAX 1000000 

int main(void) { 
    unsigned long long *numbers; 
    unsigned long long number, p; 
    int i, n, factors, count; 
    char text[100]; 

    numbers = calloc(NUMBER_MAX, sizeof(*numbers)); 
    if (numbers == NULL) { 
     printf("cannot allocate number array\n"); 
     return 1; 
    } 

    for (count = 0; count < NUMBER_MAX; count++) { 
     if (!fgets(text, sizeof text, stdin)) { 
      break; 
     } 
     if (sscanf(text, "%llu", &number) == 1 && number > 0) { 
      numbers[count] = number; 
     } else { 
      fprintf(stderr, "Error: Wrong Input!\n"); 
      return 100; 
     } 
    } 
    for (i = 0; i < count; i++) { 
     number = numbers[i]; 
     printf("Prime factorization of nubmer %llu is:\n", number); 
     factors = 0; 
     for (p = 2; p < 0x100000000 && p * p <= number; p += 1 + (p & 1)) { 
      if (number % p == 0) { 
       n = 0; 
       factors++; 
       do { 
        number /= p; 
        n++; 
       } while (number % p == 0); 
       if (n == 1) { 
        printf("%llu ", p); 
       } else { 
        printf("%llu^%d ", p, n); 
       } 
       if (number != 1) { 
        printf("* "); 
       } 
      } 
     } 
     if (factors == 0 || number != 1) { 
      printf("%llu", number); 
     } 
     printf("\n"); 
    } 
    free(numbers); 
    return 0; 
}