Recherche du facteur premier le plus élevé d'un nombre composite en c

Question

J'accepte un nombre composite en tant qu'entrée. Je veux imprimer tous ses facteurs et aussi le plus grand facteur premier de ce nombre. J'ai écrit le code suivant. Il fonctionne parfaitement jusqu'au nombre 51. Mais si un nombre supérieur à 51 est entré, une mauvaise sortie est affichée. comment puis-je corriger mon code?

#include<stdio.h> 
void main() 
{ 
int i, j, b=2, c; 
printf("\nEnter a composite number: "); 
scanf("%d", &c); 
printf("Factors: "); 

for(i=1; i<=c/2; i++) 
{ 
    if(c%i==0) 
    { 
    printf("%d ", i); 
    for(j=1; j<=i; j++) 
    { 
    if(i%j > 0) 
    { 
    b = i; 
    } 
    if(b%3==0) 
    b = 3; 
    else if(b%2==0) 
    b = 2; 
    else if(b%5==0) 
    b = 5; 
    } 
    } 
} 
printf("%d\nLargest prime factor: %d\n", c, b); 
} 

Answer 1

Vous devez recoder afin que votre code trouve tous les nombres premiers d'un nombre donné, au lieu de simplement calculer les nombres premiers 2,3 et 5. En d'autres termes, votre code ne peut fonctionner avec le nombre que vous calculez est un nombre premier ou est un multiple de 2, 3 ou 5. Mais 7, 11, 13, 17, 19 sont également des nombres premiers - ainsi votre code devrait simplement fonctionner en trouvant tous les facteurs d'un particulier numéroter et renvoyer le plus grand facteur qui n'est plus divisible.

Answer 2

Je présume que vous faites cela pour apprendre, alors j'espère que cela ne vous dérange pas. Je commencerais par passer votre algorithme sur un nombre qui échoue. Est-ce que cela vous montre où est l'erreur?

Answer 3

Ceci est un peu un spoiler, donc si vous voulez résoudre ce problème vous-même, ne lisez pas encore :). Je vais essayer de fournir des conseils en ordre de succession, de sorte que vous pouvez lire chaque indication dans l'ordre, et si vous avez besoin de plus des conseils, passer à la prochaine indication, etc.

Conseil n ° 1: Si diviseur est un diviseur de n, alors n/diviseur est aussi un diviseur de n. Par exemple, 100/2 = 50 avec le reste 0, donc 2 est un diviseur de 100. Mais cela signifie aussi que 50 est un diviseur de 100.

Astuce # 2 Compte tenu Astuce n ° 1, cela signifie est que nous pouvons boucler de i = 2 à i * i < = n lors de la vérification des facteurs premiers. Par exemple, si nous vérifions le nombre 100, nous n'avons qu'à boucler à 10 (10 * 10 est < = 100) car en utilisant l'indice # 1, nous obtiendrons tous les facteurs. C'est:

100/2 = 50, so 2 and 50 are factors 
100/5 = 20, so 5 and 20 are factors 
100/10 = 10, so 10 is a factor 

Conseil n ° 3 Puisque nous soucions que sur les facteurs principaux pour n, il est suffisant de trouver le premier facteur de n, appelez-le diviseur, et alors nous pouvons récursive trouver les autres facteurs pour n/diviseur. Nous pouvons utiliser une approche sieve et marquer les facteurs tels que nous les trouvons.

Conseil n ° 4 solution d'échantillon dans C:

bool factors[100000]; 

void getprimefactors(int n) { 
    // 0 and 1 are not prime 
    if (n == 0 || n == 1) return; 

    // find smallest number >= 2 that is a divisor of n (it will be a prime number) 
    int divisor = 0; 
    for(int i = 2; i*i <= n; ++i) { 
    if (n % i == 0) { 
     divisor = i; 
     break; 
    } 
    } 
    if (divisor == 0) { 
    // we didn't find a divisor, so n is prime 
    factors[n] = true; 
    return; 
    } 

    // we found a divisor 
    factors[divisor] = true; 
    getprimefactors(n/divisor); 
} 

int main() { 
    memset(factors,false,sizeof factors); 
    int f = 1234; 
    getprimefactors(f); 
    int largest; 
    printf("prime factors for %d:\n",f); 
    for(int i = 2; i <= f/2; ++i) { 
    if (factors[i]) { 
     printf("%d\n",i); 
     largest = i; 
    } 
    } 
    printf("largest prime factor is %d\n",largest); 
    return 0; 
} 

Sortie:

---------- Capture Output ---------- 
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe 
prime factors for 1234: 
2 
617 
largest prime factor is 617 
> Terminated with exit code 0. 

Answer 4

Vraiment, cela est très lent pour tous, mais les plus petits nombres (ci-dessous, disons, 100 000) . Essayez de trouver seulement les principaux facteurs du nombre:

#include <cmath> 

void addfactor(int n) { 
    printf ("%d\n", n); 
} 

int main() 
{ 
    int d; 
    int s; 
    int c = 1234567; 
    while (!(c&1)) { 
     addfactor(2); 
     c >>= 1; 
    } 
    while (c%3 == 0) { 
     addfactor(3); 
     c /= 3; 
    } 
    s = (int)sqrt(c + 0.5); 
    for (d = 5; d <= s;) { 
     while (c % d == 0) { 
      addfactor(d); 
      c /= d; 
      s = (int)sqrt(c + 0.5); 
     } 
     d += 2; 
     while (c % d == 0) { 
      addfactor(d); 
      c /= d; 
      s = (int)sqrt(c + 0.5); 
     } 
     d += 4; 
    } 
    if (c > 1) 
     addfactor(c); 
    return 0; 
} 

où addfactor est une sorte de macro qui ajoute le facteur à une liste de facteurs premiers. Une fois que vous les avez, vous pouvez construire une liste de tous les facteurs du nombre.

Ceci est considérablement plus rapide que les autres extraits de code publiés ici.Pour une entrée aléatoire comme 10597959011, mon code prendrait quelque chose comme des opérations de 2000 bits plus 1000 autres pour reconstituer les diviseurs, alors que les autres prendraient des milliards d'opérations. C'est la différence entre «instantané» et une minute dans ce cas.

Answer 5

Simplification à la réponse de dcp (de manière itérative):

#include <stdio.h> 
void factorize_and_print(unsigned long number) { 
    unsigned long factor; 
    for(factor = 2; number > 1; factor++) { 
    while(number % factor == 0) { 
     number = number/factor; 
     printf("%lu\n",factor); 
    } 
    } 
} 

/* example main */ 
int main(int argc,char** argv) { 
    if(argc >= 2) { 
    long number = atol(argv[1]); 
    factorize_and_print(number); 
    } else { 
    printf("Usage: %s <number>%<number> is unsigned long", argv[0]); 
    } 
} 

Note: Il y a un certain nombre bug ici l'analyse syntaxique qui ne reçoit pas le nombre argv correctement.