RELAZIONE D'INFORMATICA

TESTO:

Esiste un metodo antichissimo per trovare tutti i numeri primi compresi fra due ed N noto come Crivello di Eratostene. Esso consiste nello scrivere tutti i numeri da 2 a N e cancellare successivamente tutti i multipli di 2(escluso), tutti i multipli di 3(escluso), tutti i multipli di 5(escluso) e così via. I numeri 'sopravvissuti' saranno tutti e soli i numeri primi compresi tra due ed N.

ANALISI:

Il problema richiede di trovare tutti i numeri primi precedenti al numero fornito dall'utente con un vecchio metodo (Crivello di Eratostene). Per la risoluzione in Pascal sono indispensabili variabili di tipo ARRAY per salvare tutte le cifre in una sola variabile. Per risolvere il problema prima inserisco nella variabile di tipo Array il tutti i numeri fino al 20000, poi richiedo all'utente di quale numero vuole sapere i numeri primi precedenti ed elimino i numeri precedenti ad esso ponendoli a zero.

RAFFINAMENTO:

programma primi;

inizio

p:=1;

ripeti

numeri[p]:=p;

incrementa(p);

finchè p=20000;

num1:=1;

p:=1;

num2:=1;

inserisci('Scrivi un numero');

ricevi(num1);

mentre num2<num1 esegui

inizio

ex:=2;

p:=1;

incrementa(num2);

mentre p<num1 esegui

inizio

p:=num2*ex;

numeri[p]:=0;

incrementa(ex);

fine;

fine;

p:=1;

ripeti

se numeri[p]<>0 allora

inserisci(numeri[p],'-');

incrementa(p);

finchè p=num1+1;

fine.

PROGRAMMA:

program primi;

uses crt;

var numeri:array[1..20000] of Integer;

num1,num2,ex,p:integer;

begin

p:=1;

repeat

numeri[p]:=p;

inc(p);

until p=20000;

clrscr;

num1:=1;

p:=1;

num2:=1;

writeln('Scrivi un numero');

Readln(num1);

while num2<num1 do

begin

ex:=2;

p:=1;

inc(num2);

while p<num1 do

begin

p:=num2*ex;

numeri[p]:=0;

inc(ex);

end;

end;

p:=1;

repeat

if numeri[p]<>0 then

write(numeri[p],'-');

inc(p);

until p=num1+1;

readln;

end.