Facteurs premiers en C

Je suis tombé sur ce programme efficace pour imprimer tous les facteurs premiers d’un nombre donné:

# include  # include  // A function to print all prime factors of a given number n void primeFactors(int n) { // Print the number of 2s that divide n while (n%2 == 0) { printf("%d ", 2); n = n/2; } // n must be odd at this point. So we can skip // one element (Note i = i +2) for (int i = 3; i  2&&n%2!=0) printf ("%d ", n); } /* Driver program to test above function */ int main() { int n = 315; primeFactors(n); return 0; } 

La sortie est 3 3 5 7. C’est parfait.

Mais j’ai une confusion dans cet algorithme. sqrt() renvoie une valeur flottante. S’il est affiché au format entier dans printf , il renvoie un nombre aléatoire élevé. Si tel est le cas, la condition de la boucle for doit échouer, car sqrt() en tant qu’entier renvoie un nombre aléatoire. Quelqu’un pourrait-il expliquer cela?

De plus, quelqu’un pourrait-il vérifier cela? Cet algorithme a été mal écrit dans le site Web geeksforgeeks comme si (n> 2) au lieu de si (n> 2 && n! = 0), qui a été ajouté par moi. Quelqu’un s’il vous plaît vérifier cet algorithme. Merci d’avance.

    Si vous essayez d’afficher la valeur de sqrt(n) comme s’il s’agissait d’un entier:

     printf("sqrt(n) = %d\n", sqrt(n)); // Don't do this 

    alors vous avez un comportement indéfini. sqrt() renvoie un résultat de type double . Le compilateur ne sait pas (ou n’est pas obligé de savoir) le type attendu de l’argument. C’est à vous de passer un argument du type correct. L’appel ci-dessus à printf a un comportement indéfini.

    Dans d’autres contextes, où le type et le type attendu d’une expression sont non ambigus, le langage nécessite des conversions implicites. En particulier, dans l’expression i <= sqrt(n) , où i et n sont de type int , l’argument n est converti d’ int en double (type de paramètre pour sqrt() ) , and the value of i is also converted from int to double`. Le résultat sera probablement ce que vous espériez.

    Incidemment, ceci:

     for (int i = 3; i <= sqrt(n); i = i+2) ... 

    est susceptible d'être inefficace. La fonction sqrt est relativement chère et sera appelée à chaque itération de la boucle. (Le précalculateur sqrt(n) est une bonne solution dans certains cas, mais ici la valeur de n peut changer dans la boucle.)

    Une alternative est:

     for (int i = 3; i*i <= n; i += 2) ... 

    ce qui évite les complications de l'arithmétique en virgule flottante (mais réfléchissez si i*i peut déborder).

    (Ce serait bien si C avait une fonction de racine carrée entière dans la bibliothèque standard, mais ce n’est pas le cas.)

    D’après ce que j’ai compris de votre question, vous passez de float à la fonction printf() avec le spécificateur %d qui est un integer . C’est un comportement indéfini .

    N1570 7.21.6.1 paragraphe 9:

    … Si l’un des arguments n’est pas du type correct pour la spécification de conversion correspondante, le comportement est indéfini.

    C’est pourquoi vous voyez la valeur de la poubelle. Le compilateur peut vous avertir mais ne pas commettre d’erreur lors de la compilation ou de l’exécution, car C n’est pas un langage ssortingctement typé .

    entrez la description de l'image ici

    Il a été compilé avec succès mais sa sortie est -376018152 . Encore une fois, c’est UB.

    D’autres ont suggéré de pré-calculer la racine carrée entière, mais vous devez faire attention de la recalculer si nécessaire. Pour la boucle principale, je voudrais utiliser quelque chose comme:

     // n must be odd at this point. So we can skip // one element (Note i = i +2) int limit = isqrt(n); // Calculate integer square root. for (int i = 3; i <= limit; i = i+2) { // While i divides n, print i and divide n if (n % i == 0) { printf("%d ", i); n = n / i; while (n%i == 0) { printf("%d ", i); n = n / i; } // Recalculate limit as n has changed. limit = isqrt(n); } } 

    Cela recalcule la racine carrée uniquement lorsque le nombre testé est modifié. J'utilise isqrt(n) pour indiquer la fonction permettant d'effectuer le calcul réel. J'utilise Newton-Raphson dans mon propre code, mais il existe d'autres méthodes possibles.

    Votre test à la fin pourrait être simplifié à:

     // This condition is to handle the case when n // is a prime number greater than 2 if (n > 1) { printf ("%d ", n); } 

    Il y a au plus un facteur premier plus grand que la racine carrée d'un nombre. Ce seul facteur (le cas échéant) sera le rest après la division de tous les facteurs premiers plus petits.