J'essaie de trouver le plus grand facteur premier d'un grand nombre en C, pour de petits nombres comme 100 ou même 10000, cela fonctionne bien mais échoue (par échec, je veux dire qu'il continue à fonctionner et à fonctionner pendant des dizaines de minutes sur mon core2duo et i5) pour les très gros numéros target (voir le code pour le numéro cible.) Mon algorithme est-il correct?

Je suis nouveau en C et j'ai vraiment du mal avec de gros chiffres. Ce que je veux, c'est une correction ou des conseils, pas une solution.Je peux le faire en utilisant python avec des liaisons bignum et des trucs ( je n'ai pas encore essayé mais je suis presque sûr ) mais pas en C. Ou j'aurais pu en faire petite erreur que je suis trop fatigué pour réaliser, en tout cas voici le code que j'ai écrit:

#include <stdio.h>
// To find largest prime factor of target
int is_prime(unsigned long long int num);

long int main(void) {
    unsigned long long int target = 600851475143;
    unsigned long long int current_factor = 1;
    register unsigned long long int i = 2;
    while (i < target) {
        if ( (target % i) == 0  && is_prime(i) && (i > current_factor) ) { //verify i as a prime factor and greater than last factor
            current_factor = i;
        }
        i++;
    }
    printf("The greates is: %llu \n",current_factor);
return(0);
}


int is_prime (unsigned long long int num) { //if num is prime 1 else 0 
    unsigned long long int z = 2;
    while (num > z && z !=num) {
        if ((num % z) == 0) {return 0;}
        z++;
    }

return 1;
}
-2
Ubdus Samad 30 déc. 2017 à 20:15

4 réponses

Meilleure réponse

600 milliards d'itérations de n'importe quoi prendront un temps non négligeable. Vous devez réduire considérablement cela.

Voici un indice: étant donné une valeur entière arbitraire x, si nous découvrons que y est un facteur, alors nous avons implicitement découvert que x / y est également un facteur. En d'autres termes, les facteurs viennent toujours par paires. Il y a donc une limite à la distance à parcourir avant d'effectuer un travail redondant.

Quelle est cette limite? Eh bien, quel est le point de croisement où y sera supérieur à x / y?

Une fois que vous avez appliqué cette optimisation à la boucle externe, vous constaterez que l'exécution de votre code sera limitée par la fonction is_prime. Mais bien sûr, vous pouvez également appliquer une technique similaire à cela.

4
Oliver Charlesworth 30 déc. 2017 à 18:21

Le code a 2 problèmes majeurs

  1. La boucle while (i < target) est très inefficace. Après avoir trouvé un facteur, target pourrait être réduit à target = target / i;. De plus, un facteur i peut se produire plusieurs fois. Correction non affichée.

  2. is_prime(n) est très inefficace. Son while (num > z && z !=num) pourrait boucler n temps. Ici aussi, utilisez le quotient pour limiter les itérations à sqrt(n) fois.

    int is_prime (unsigned long long int num) {
      unsigned long long int z = 2;
      while (z <= num/z) {
        if ((num % z) == 0) return 0;
        z++;
      }
      return num > 1;
    }
    
2
chux - Reinstate Monica 30 déc. 2017 à 18:00

Rien ne va pas, il faut juste une optimisation, par exemple:

int    is_prime(unsigned long long int num) { 
    if (num == 2) {
        return (1);                /* Special case */
    }
    if (num % 2 == 0 || num <= 1) {
         return (0);
    }
    unsigned long long int z = 3;  /* We skipped the all even numbers */
    while (z < num) {              /* Do a single test instead of your redundant ones */
        if ((num % z) == 0) {
            return 0;
        }
        z += 2;                     /* Here we go twice as fast */
    }
return 1;
}

Le gros autre problème est aussi while (z

EDIT: Quelqu'un d'autre a posté 50 secondes avant moi la solution de tableau de nombres premiers qui est la meilleure, mais j'ai choisi de donner une solution simple car vous n'êtes qu'un débutant et manipuler des tableaux peut ne pas être facile au début (besoin d'apprendre des pointeurs et des trucs ).

0
ft_error 30 déc. 2017 à 17:32

is_prime a un problème de poule et d'oeuf en ce que vous devez tester num uniquement par rapport à d'autres nombres premiers. Vous n'avez donc pas besoin de vérifier 9 car c'est un multiple de 3.

is_prime pourrait maintenir un tableau de nombres premiers et chaque fois qu'un nouveau num est testé qui est un pime, il peut être ajouté au tableau. num est testé par rapport à chaque premier du tableau et s'il n'est divisible par aucun des nombres premiers du tableau, il est lui-même un nombre premier et est ajouté au tableau. L'array doit être malléable et réorganisé à moins qu'il n'y ait une formue pour calculer le nombre de nombres premiers jusqu'à votre cible (je crois qu'une telle formule n'existe pas).

EDIT: le nombre de nombres premiers à tester pour la cible 600.851.475.143 sera d'environ 7.500.000.000 et la table pourrait manquer de mémoire.

L'approche peut être adaptée comme suit:

  • utiliser unsiged int jusqu'aux nombres premiers de UINT_max

  • utiliser unsigned long long int pour les nombres premiers au-dessus de cela

  • pour utiliser la force brute au-dessus d'une certaine consommation de mémoire.

UINT_MAX est défini comme 4 294 967 295 et couvrirait les nombres premiers jusqu'à environ 100 000 000 000 et coûterait 7,5 * 4 = 30 Go

Voir également The Prime Pages.

0
Paul Ogilvie 30 déc. 2017 à 18:06