PDA

Visualizza la versione completa : [pascal] numeri primi


Porippoppero
11-02-2004, 15:03
Scrivere un programma che verifichi se due numeri A e B sono primi fra loro (cioè quando non hanno divisori in comune eccetto i lnuemro 1).

Aiutatemi please :(

LeleFT
11-02-2004, 19:12
Un po' spartano, magari, e probabilmente migliorabile dal punto di vista dell'efficienza, però il suo lavoro lo fa ed è anche molto semplice:


Program DivisoriPrimi;

Uses Crt;

Var a:integer; (* primo numero *)
b:integer; (* secondo numero *)
tmp:integer; (* variabile che conterrà l'i-esimo divisore *)
min: integer; (* il minimo fra a e b *)
max: integer; (* il massimo fra a e b *)
trovato: boolean; (* flag: true se esiste un divisore comune *)

Begin
clrscr;
Write('Introdurre primo valore: ');
Readln(a);
Write('Introdurre secondo valore: ');
Readln(b);
If (a<b) Then
Begin
min := a;
max := b;
End
Else
Begin
min := b;
max := a;
End;

trovato := false;
tmp := min;
While (Not(Trovato) And (tmp > 1)) do
Begin
If (((min mod tmp) = 0) and ((max mod tmp) = 0)) Then
trovato := true
Else
tmp := tmp - 1;
End;

If (trovato) Then
Writeln('I due numeri non sono primi tra di loro: ',tmp,' li divide!')
Else
Writeln('I due numeri sono primi tra di loro!');

End.
Spiegazione: trova il minimo fra 'a' e 'b' così da "ottimizzare" la ricerca di un divisore (basta provare quelli più piccoli o al massimo uguali al minimo fra i due numeri: un numero non può dividerne uno più piccolo :D ).
Poi comincia a provare a dividere sia 'a' sia 'b' per tutti i valori a partire dal minimo fino ad arrivare a 1 (escluso, so già che li dividerà entrambi). Se ne trova uno che li divide entrambi pone 'trovato' a true ed esce dal ciclo, altrimenti esce con 'tmp' = 1 che significa che non ne esistono.

Per speigazioni ulteriori sono qui!

Ciao. :ciauz:

Porippoppero
12-02-2004, 15:46
Sei un grande, spero di poter ricambiare :) :) :)

LeleFT
12-02-2004, 15:59
Ma non c'è di che... volendo si potrebbe ottimizzare il codice in modo da non dover controllare per tutti i numeri minori al minimo fra 'a' e 'b', ma solamente controllare per i numeri inferiori alla radice del minimo. La cosa, poi, potrebbe essere applicata ricorsivamente ma diventa un po' ingestibile.


Ciao. :ciauz:

Loading