PGCD fonction de C

Q 1. Problème 5 (divisible) j'ai essayé la méthode de force brute, mais il a fallu du temps, j'ai donc appelé quelques sites et j'ai trouvé ce code:

#include<stdio.h>
int gcd(int a, int b)
{
    while (b != 0)
    {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return a;
}

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

int main()
{
    int res = 1;
    int i;
    for (i = 2; i <= 20; i++)
    {
        res = lcm(res, i);
    }

    printf("%d\n", res);
    return 0;
}

C'est très simple mais je ne comprends pas comment la fonction "pgcd" fonctionne; quelqu'un peut-il m'aider à comprendre la logique. (Je sais qu'il renvoie le PGCD de 2 nombres, mais pourquoi tant de nombreuses opérations?)

Bienvenue à Débordement de Pile! Nous sommes beaucoup plus susceptibles d'être en mesure de vous aider si vous prenez une fissure à vous-même le problème et décrivez ce que vous avez essayé. Vous apprendrez également plus de cette façon, et votre but est d'apprendre le C, à droite? 🙂 Bonne chance et amusez-vous!
Google de la recherche pour "Tamis Eratosthène" conduit à de nombreux sites qui l'expliquent. Si votre moteur de recherche ne fonctionne pas, il est temps de changer.
Bienvenue sur StackOverflow. Ce site est conçu autour de la notion d'une question par post. Vous avez clairement demandé à trois totalement différentes questions (une question de résolution de 7, un problème de 5, et un sur le Tamis de Erasosthenes). Veuillez modifier votre question et retirez les deux d'entre eux; vous pouvez écrire distinct des postes et demander à chacun des autres séparément. Lors du montage, vous pouvez également changer le sujet pour quelque chose d'utile. "Projet Euler doutes" est dénuée de sens pour de futures recherches ici. Le centre d'aide et tour les pages avoir plus d'informations sur comment cela fonctionne, si vous en avez besoin. Merci. 🙂
C'est drôle code pour le PGCD. Le 3 xor opérations de swap a et b, mais il est plus facile d'écrire:

int gcd(int x, int y) { 	int r;  	if (x <= 0 || y <= 0) 		return(0);  	while ((r = x % y) != 0) 	{ 		x = y; 		y = r; 	} 	return(y); }

Oui, il utilise une variable locale dont le code que vous avez trouvé n'est pas, mais ce n'est pas un coût dramatiques. Je remarque qu'il y a au moins deux autres questions à propos d'Euler Projet 5 (Euler Projet 5 et Euler Projet 5).

OriginalL'auteur Faizaan Mohammed | 2013-11-02

13

À votre deuxième question: Le PGCD fonction utilise D'euclide l'Algorithme. Il calcule A mod B, procède à un échange de A et B avec un XOR swap. Une version plus lisible pourrait ressembler à ceci:
```
int gcd(int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;

        a = b;
        b = temp;
    }
    return a;
}
```
OriginalL'auteur Jack
5

Ce problème peut également être résolu très propre chemin avec la récursivité:
```
int gcd(int a, int b) {
    int remainder = a % b;

    if (remainder == 0) {
        return b;
    }

    return gcd(b, remainder);
}
```
Une solution récursive qui peut être écrit comme une simple boucle est mauvaise utilisation de la récursivité.
c'est très propre solution et plus compréhensible que l'on a accepté la réponse. plus un !

OriginalL'auteur

J'ai exécuté cette consolidés pour PGCD :

#include<stdio.h>
#include<conio.h>
int main(){
   int l, s,r;

   printf("\n\tEnter value : ");
   scanf("%d %d",&l,&s);

  while(l%s!=0){
    r=l%s;
    l=s;
    s=r;
  }
  printf("\n\tGCD = %d",s);
  getch();
}

OriginalL'auteur Omar Faruk

À l'aide d'un peu de récursivité et de l'Objective-C

-(int)euclid:(int)numA numB:(int)numB
{
    if (numB == 0)
        return numA;
    else
        return ([self euclid:numB numB:numA % numB]);
}

OriginalL'auteur Trygve

Vous devez vous connecter pour publier un commentaire.