[Algoritmi] Determinazione di numeri primi tra loro

[daneel]

Devo lavorare con un algoritmo non dipendente dal linguaggio che, dati due numeri, verifichi che siano o meno primi tra loro.
Ho pensato che potrebbe essere realizzato inserendo in due array con due semplici cicli i divisori di ciascuno dei due argomenti della funzione e confrontando quindi una ad una tutte le posizioni dei due array risultanti (individuato il primo divisore comune la funzione potrebbe essere terminata immediatamente), ma se qualcuno conoscesse un algoritmo più efficiente sarei felice di utilizzarlo.

[Xadoom]

Scusa ma che intendi per "primi tra loro"?
Che non abbiano divisori comuni?

[Xadoom]

Se ho immaginato bene un algoritmo migliore sarebbe:

num1 e num2

div = {...} array dei divisori di num1

ciclo per i che va da 0 a lunghezza di div
if(resto di (num2/div[i]) uguale a zero) num1 e num2 non sono primi tra loro!


Spero di essermi fatto capire...ho cercato di prescindere dal linguaggio!
Cmq in linea di massima è come hai detto tu, solo con un solo array a con meno verifiche

Ciao

[Andrea Simonassi]

basta testare che il MCD(a,b) sia 1, usando l'algoritmo di euclide.

[Dwenegar]

Due numeri sono coprimi se il loro Massimo Comune Divisore è 1.

Puoi utilizzare l'algoritmo di Euclide per determinare il MCD dei due numeri. L'algoritmo è:

mcd(a, b)
    while (b != 0)
        swap(a, b)
        b = b mod a

    return a

[Dwenegar]

Arghhhh...fregato sul tempo

[Andrea Simonassi]

Flash, a haaaaaaaa .......

[daneel]

L'algoritmo di Euclide è perfetto, considerando che devo lanciarlo circa 40000 volte ad ogni esecuzione del programma
Grazie.

[blinkago]

Cosa devi fare???

[daneel]

Oltre alle applicazioni in cui devo usarlo seriamente, avevo intenzione di realizzare un grigliato in cui le varie caselle vengono colorate in base ad alcune funzioni matematiche.