можно ли оптимизировать?

http://www.helloworld.ru/texts/comp/algor/chisl/simple/index.htm
http://arti.kz/555-об-одном-алгоритме-поиска-простых-чис
Во-первых, не имеет никакого смысла проверять, делится ли число п на k, если k больше квадратного корня из п, потому что по крайней мере один делитель числа п, если он есть, не должен превосходить квадратного корня из п, а одного делителя уже достаточно, чтобы считать число составным

Существует также знаменитая арифметическая теорема, которая гласит, что любое целое число можно представить в виде произведения простых чисел, и это произведение единственное. Число не является составным, если оно не делится ни на одно простое число, меньшее себя.

r= 1
p(1)= 2
for n= 3 to 1000
k= 1
f=1
while f=1 and p(k )<= sqrt (n )
test=rem (n/p (k ))
if test =0 then f=0
k= k + 1
if f=1 then r= r + 1
P (r)= n

На компьютерном графике составные числа представлены маленькими белыми квадратиками, а простые — черными.

Да! Самое элементарное, дело в том что невозможно получить целое число поделив X/M при N>M, а простое число не может делиться на число большее чем оно само кроме себя. В вашем случае "X" - это множество чисел второй половины проверяемого диапазона. ТОЕСТЬ мы просто отсекаем вторую часть диапазона (считаем от I до N/2 ), так как в любом случае целых делителей простое число там иметь не может. А значит и время работы алгоритма укоротится вдвое.

Для этого после чтения вашей переменной "n" запишите строку:

n := n / 2;

Второй шаг оптимизации - это использование ассемблерной вставки в месте проверки числа на предмет "простоты".
Весь компот... если придумаю ещё че - напишу.

массив от 1 до 2000000?