[PASCAL] Problema elementare.

[Rhaegar20]

Salve a tutti. Ho da pochissimo iniziato a studiare, per conto mio e interesse personale, un po' di programmazione. Provando a risolvere un problema mi son trovato davanti ad un errore, sicuramente commesso da me, che però non riesco ad individuare e che mi sta facendo uscir pazzo. :confused:
L'esercizio in questione chiede di crear una funzione che elenchi i primi 50 numeri primi, ed io son arrivato a scriver questo algoritmo:

var a,c,n,d:integer;

begin
a:=2;
write(a,' ');
c:=1;
n:=3;
repeat
d:=2;
while d<n do
begin
if n mod d =0 then
n:=n+1;
d:=d+1
end;
write(n,' ');
n:=n+1;
c:=c+1;
until(c=50);
end.

Il programma, sino al numero primo 83, parrebbe funzionare. Ma, da lì in poi, lista numeri (come 87 e 95) che primi non sono, secondo una logica che proprio mi sfugge. Ci sarebbe qualcuno di così buon cuore da aiutarmi a capire cosa va storto? :)

[wingman87]

Metti sempre il tag code intorno al codice, così mantieni l'indentazione
begin
a:=2;
write(a,' ');
c:=1;
n:=3;
repeat
d:=2;
while d<n do
begin
if n mod d =0 then
n:=n+1;
d:=d+1
end;
write(n,' ');
n:=n+1;
c:=c+1;
until(c=50);
end
Il problema è nella parte in rosso. Prova a rifletterci ancora un po' focalizzando l'attenzione su quella parte...

[Rhaegar20]

Grazie per l'attenzione innanzitutto. :)
Sì, immaginavo che il problema fosse in quelle righe, ed infatti ho provato diverse variazioni di codice. Ma il risultato che son riuscito ad ottenere è rimasto lo stesso.
Riguardando la lista di numeri in output, comunque, mi son reso conto di aver scritto un'inesattezza, prima: ci son "errori" anche prima del numero 83.

[wingman87]

Ok, il problema è questo: il ragionamento che hai fatto è corretto cioè, per ogni numero, provi a dividerlo per tutti i numeri inferiori (while d<n do ...).
Nel codice che hai scritto però cosa succede, ad esempio, se un numero non è divisibile per 2,3,4 ma è divisibile per 5? Ad esempio 25? Immagino che tra i primi rilevati dal tuo programma c'è anche il 27 giusto?
In sostanza è sbagliato quello che fai quando rilevi che un numero è divisibile per un altro numero inferiore e quindi non è primo.

[Rhaegar20]

Esatto, 27 è proprio il 'primo' dei numeri non-primi che compare nell'elenco. Solo, continua a sfuggirmi il perchè. Ne comprendo perchè il problema si pone proprio a partir da quel valore. Credo d'aver capito che l'errore sta nell'assegnare ad n il valore di n+1 ogni qual volta trovo un divisore, ma non riesco a trovar un altro percorso logico valido.

P.S. Ad ogni modo, la ringrazio del tempo che dedica ad un neofita.

[wingman87]

Prego, spero di riuscire a spiegarmi...
Facciamo così, analizziamo la parte di codice interessata:

while d<n do
begin
if n mod d =0 then
n:=n+1;
d:=d+1
end;
write(n,' ');

Ed eseguiamola "a mano" ponendoci già nella situazione n=25 e d=5.

d<n ? sì, quindi eseguo il corpo del ciclo
n mod d=0 ? Sì, quindi n=26
d=6 //Qui c'è l'errore
d<n ? sì, quindi rieseguo il corpo del ciclo
n mod d=0 ? No
d=7
d<n ? sì, quindi rieseguo il corpo del ciclo
n mod d=0 ? No
d=8
d<n ? sì, quindi rieseguo il corpo del ciclo
...
... // Viene rieseguito più volte il ciclo, intanto d cresce
...
d=13
d<n ? sì, quindi rieseguo il corpo del ciclo
n mod d=0 ? Sì, quindi n=27
d=14
...
... // Viene rieseguito più volte il ciclo, intanto d cresce
d=27
d<n ? no, quindi esco dal ciclo
stampo n cioè 27

[Rhaegar20]

La ringrazio infinitamente della spiegazione, credo di aver capito dove sbagliavo. Ho corretto l'algoritmo in questo modo:


while d<n do
begin
if n mod d =0 then
begin
n:=n+1;
d:=2
end
else
d:=d+1
end;


e pare funzionare, almeno per i primi 50 numeri primi. :D

[wingman87]

Sì ora è corretto :)
La mia spiegazione era un po' arzigogolata ma sono contento che abbia capito.