Простые числа

Есть несколько способов найти все простые числа или определить, что число простое. Рассмотрим первый который приходит обычно начинающим программистам (будем рассматривать только основной код):

readln(n);
if n=1 then write('число не простое')
else begin  
simply:=true; //предположим, что n - простое, проверим обратное 
for i:=2 to n-1 do
if n mod i = 0 then begin
write('число не простое');
simply:=false;
break;//выход из цикла
end;
if simply then write('число простое');
end;
Второй способ более рационален и чаще всего используется. Это просто немного модифицированный первый способ, только проверяем делимость до корня квадратного из n (это предположение доказывается в курсе алгебры вуза, здесь мы его только применяем):
readln(n);
if n=1 then write('число не простое')
else begin  
simply:=true;  

for i:=2 to round(sqrt(n)) do
if n mod i = 0 then begin
write('число не простое');
simply:=false;

break;

end;
if simply then write('число простое');
end;
Есть другой способ этого же метода, только используется цикл "пока", где проверяется только нечетные делители. Перед этим проверяется число на четность и обязательно исключить 2.
readln(n);
if n=1 then write('число не простое')
else if n=2 then write('число простое')
else if n mod 2 = 0 then write('число не простое')
else begin 
simply:=true;

i:=3;
k:=round(sqrt(n));
while i<=k do
begin
if n mod i = 0 then 
begin
write('число не простое');
simply:=false;

break;

end;
inc(i,2);
end;
if simply then write('число простое');
end;
Если число n достаточно большое (типа longint например), то лучше использовать второй пример. Цикл for работает как счетчик и не требует дополнительных проверок как в цикле while, поэтому будет работать быстрее.
Еще один алгоритм нахождения всех простых чисел - это решето Эратосфена. Пусть все числа являются индексами массива 
a:array[1..1000]of boolean;

Предположим, что все числа простые. Для задания наальных значений используем функцию

fillchar(a,sizeof(a),true); 

Проверяем каждый раз на делимость новое найденное простое число:

a[1]:=false;a[2]:=true;
for i:=2 to n-1 do
if a[i] then begin
 k:=i;
 for j:=i+1 to n do
  //исключаем из списка простых чисел, то число, которое делится на текущее простое число 
 if a[j] and (j mod k=0) then a[j]:=false; 
 end;
//выводим все простые числа
for i:=1 to n do
if a[i] then write(i,' ');
Этот алгоритм действует только до чисел типа integer, так как массив принимает индексы только этого типа. В новых версиях компиляторов языка Паскаль: Free Рascal, Delphi, Lazarus - можно использовать динамический массив:

var a:array of boolean;

В программе после ввода числа n используем процедуру задания размера
setlength(a,n+1);
и задания начальных данных
for i:=1 to n do a[i]:=true;
В днамическом массиве нумерация начинается с 0. 

Только для больших чисел все равно будет считать долго. Лучше применить третий или второй вариант, изменив вывод: вместо сообщения простое или нет число, выводить только простые числа:
readln(n);
if n=1 then exit; //конец процедуры или программы 
for i:=2 to n do
if i=2 then write(i,' ')
else if i mod 2 = 0 then continue
else begin
simply:=true;
k:=round(sqrt(i));
j:=3;
while j<=k do
begin
if i mod j = 0 then
begin
 simply:=false;
 break;
end;
inc(j,2);
end;
if simply then write(i,' ');
end;

Если нужно запомнить все простые числа в массив, используем следующий вариант:
readln(n);j:=0;
if n=1 then exit;
for i:=2 to n do begin
 if i=2 then begin inc(j);a[j]:=i end //добавим первое простое число в массив

 else if i mod 2 = 0 then continue;//исключаем четные числа

simply:=true;

for k:=1 to j do //проверяем на делимость простых чисел

if i mod a[k] = 0 then
begin
simply:=false;
break;
end; 
//добавим в массив следующее простое число
if simply then begin inc(j);a[j]:=i end;
end;

 for i:=1 to j do write(a[i],' ');

Массив нужно объявлять либо статическим, либо динамическим (см. примеры выше).Если массив большой и типа longint, то можно размер динамического массива менять по мере добавления простых чисел в массив:

var n,i,k,j:longint;
    simply:boolean;
    a:array of longint;//массив ОБЯЗАТЕЛЬНО нужно прописать последним, чтобы не было перекрытия области уже объявленных переменных

begin

readln(n);j:=0;setlength(a,1);
if n=1 then exit;
for i:=2 to n do begin
 if i=2 then begin inc(j);a[j-1]:=i end //добавим первое простое число в массив
 else if i mod 2 = 0 then continue;//исключаем четные числа
simply:=true;
for k:=0 to j-1 do //проверяем на делимость простых чисел
if i mod a[k] = 0 then
begin
simply:=false;
break;
end;
//добавим в массив следующее простое число
if simply then begin inc(j);setlength(a,j);a[j-1]:=i; end;
end;
for i:=0 to j-1 do write(a[i],' ');
 writeln(j);  

end.

Ну вот вроде и все.