[C] Calcolare MCD senza usare il metodo di Euclide

[21Edoardo96]

Ciao,
devo scrivere un programma che permetta all'utente di trovare il MCD tra 2 numeri interi (per comodità adesso ho imposto che siano minori di 100'000)non negativi, il problema è che non devo farlo utilizzando il metodo di Euclide ma bensì il metodo usato alle scuole medie ossia:
1)Nel caso in cui num1=num2 il MCD è num1;
2)Se questo non è vero allora bisogna verificare se il primo numero inserito è primo e se questa condizione è vera il MCD è 1;
3)Se neppure questa condizione è vera bisogna verificare se il secondo numero è primo e se questa condizione è vera il MCD è 1;
4)Se neppure dopo il passaggio non si è trovato il MCD si inizia con la fattorizzazione in numeri primi;
5)Si moltiplicano i numeri primi comuni con l'esponente minore ricavati dalla fattorizzazione e si ottiene il MCD.

//Calcolo del MCD usando il metodo tradizionale
#include<stdio.h>
main()
{
   int a, b,i, j, primo, MCD;
   printf("Calcolo del MCD tra 2 numeri:\n\n");
   for (i=2; i<=100; i++)
      {
          primo= 0; //Inizializzazione della variabile primo 
            for(j=2; j<i; j++)
            {  
                 if(i%j!=0)//Scorre tutti i divisori del numero i(dal numero 2)
                 { 
                      primo++; 
                 }
            }
                     if (primo==i-2)
                     {//Se tutti i numeri precedenti(all'i-esimo numero) divisi per l'i-esimo numero
                      //hanno dato resto diverso da 0 
                      printf("%d\t", i); //Allora l'i-esimo numero è un numero primo
                     }
       }
   printf("Inserire il primo numero intero non negativo:\n");
   scanf("%d",&a);
   printf("Inserire il secondo numero intero non negativo:\n");
   scanf("%d",&b);      
   if(a==b)
   {
        MCD=a;
        printf("Il MCD tra %d e %d e\':%d",a,b,MCD);
   } 
   else
   {
        if(a==primo)
        { 
            printf("Il MCD tra %d e %d e\':1",a,b,); 
        }
        else
            {
                if(b==primo)
                {
                    printf("Il MCD tra %d e %d e\':1",a,b,);
                }
                else
                {
                    //Fattorizzare in numeri primi
                }
            }
    }                             
system("pause");
}

I problemi che riscontro sostanzialmente sono 3:
1)Il primo numero primo che mi appare è 2 e non è 1;
2)Il compilatore mi da un errore sintattico prima del primo printf("Il MCD tra %d e %d e\':1",a,b,);
3)Ho guardato altri forum per capire come fare la fattorizzazione in numeri primi ma non sono riuscito a capire (dove ci sarebbe dovuta essere la fattorizzazione ho scritto semplicemente //Fattorizzare in numeri primi non sapendo cosa fare).

Come posso fare per risolveli?

Vi ringrazio anticipatamente.

[oregon]

Cosa ci fa l'ultima virgola?

printf("Il MCD tra %d e %d e':1",a,b,);

[21Edoardo96]

Grazie ho sistemato alcune cose in questo nuovo codice,
però risolto questo problema rimangono gli altri 2 e sene è aggiunto un altro, ossia che dopo aver inserito a, b non mi appare niente a schermo (a=13 e b=14 quindi non deve fare neanchela fattorizzazione in fattori primi dato che se a=primo mi dovrebbe dare subito MCD :1) ma così non è.
Volevo rettificare una cosa: i numeri primi che cerca sono i primi 1'000 e non i primi 100'000 come affermato in precedenza.
faccio apparire i numeri primi a schermo solo in questa bozza di programma, perchè in quello completo non dovrà apparire.

//Calcolo del MCD usando il metodo tradizionale
#include<stdio.h>
main()
{
   int a, b,i, j, primo, MCD;
   printf("Calcolo del MCD tra 2 numeri:\n\n");
   for (i=2; i<=100; i++)
      {
          primo= 0; //Inizializzazione della variabile primo 
            for(j=2; j<i; j++)
            {  
                 if(i%j!=0)//Scorre tutti i divisori del numero i(dal numero 2)
                 { 
                      primo++; 
                 }
            }
                     if (primo==i-2)
                     {//Se tutti i numeri precedenti(all'i-esimo numero) divisi per l'i-esimo numero
                      //hanno dato resto diverso da 0 
                      printf("%d\t", i); //Allora l'i-esimo numero è un numero primo
                     }
       }
   printf("\n");
   printf("Inserire il primo numero intero non negativo:\n");
   scanf("%d",&a);
   printf("Inserire il secondo numero intero non negativo:\n");
   scanf("%d",&b);      
   if(a==b)
   {
        MCD=a;
        printf("Il MCD tra %d e %d e\':%d",a,b,MCD);
   } 
   else
   {
        if(a==primo)
        { 
            printf("Il MCD tra %d e %d e\':1",a,b); 
        }
        else
            {
                if(b==primo)
                {
                    printf("Il MCD tra %d e %d e\':1",a,b);
                }
                else
                {
                    //Fattorizzare in numeri primi
                }
            }
    }                             
system("PAUSE");
}

[21Edoardo96]

Ciao,
sono riuscito a trovare la soluzione

#include<stdio.h>
main()
{
   int a, b,cont;
   printf("Calcolo del MCD tra 2 numeri\n\n");
   printf("\n");
   printf("Inserire il primo numero intero positivo:\n");
   scanf("%d",&a);
   printf("Inserire il secondo numero intero positivo:\n");
   scanf("%d",&b);      
   if(a==b)
   {
        printf("Il MCD tra %d e %d e\':%d",a,b,a);
   } 
   else
   {
        if(a>b)
        { 
            cont=b;
            while((a%cont!=0)||(b%cont!=0))
            {
                cont--;
            }
        printf("Il MCD tra %d e %d e\':%d",a,b,cont);        
        }
        else
        {
            cont=a;
            while((a%cont!=0)||(b%cont!=0))
            {
                cont--;
            }
        printf("Il MCD tra %d e %d e\':%d",a,b,cont);        
        }
    } 
    printf("\n");
    system("PAUSE");
}

Ciao e grazie comunque per l'aiuto

[BLACKDADO55]

potreste farlo con 4 numeri ?
ho provato, ma non mi viene !

[oregon]

Il MCD è una operazione associativa quindi puoi usare più volte la stessa funzione ...

MCD(MCD(a, b), MCD(c, d))