Просто нашел в поиске вот это и что-то сомневаюсь, что там верные данные
Да, очень странная программа: искать решетом Эратосфена простые числа до миллиона 274 секунды - это надо очень постараться. Оно должно за секунду-другую справляться в крайнем случае.
Я на Паскале практически не пишу, так что стандартной функции для получения точного времени не знаю (подозреваю, что её вообще нет). Прошу знатоков предложить стандартный метод.
Есть для неточного. Подключаем sysutils и используем функцию now. Получится примерно следующее (я внес некоторые правки и в прочий код):
Код:
Program primes;
uses Sysutils;
{ Count number of primes up to n using simple sieve of Eratosthenes. }
Function prime_count1(n : longint) : longint;
Type
TSieve = Array[0..100*1000*1000] of Boolean;
PSieve = ^TSieve;
Var
i : longint;
j : longint;
prime_count : longint;
prime : PSieve; { dynamically allocated array for the sieve }
begin
GetMem(prime, (n+1)*sizeof(Boolean)); { allocate the sieve array }
FillChar(prime^, (n+1)*sizeof(Boolean), True); { fill it with ones }
prime_count := 0;
for i := 2 to n do
begin
if prime^[i] then { next prime found }
begin
Inc(prime_count);
{ mark all multiplies as non-primes: }
j := i*2;
while j <= n do
begin
prime^[j] := False;
Inc(j, i);
end;
end;
end;
FreeMem(prime, (n+1)*sizeof(Boolean)); { free sieve array }
prime_count1 := prime_count;
end;
{ run prime counting function and determine its runtime }
Procedure test1(n : longint);
Var
count : longint;
time : Real;
begin
time := now;
count := prime_count1(n);
time := (now - time)*86400;
WriteLn('Number of primes up to ',n,' - ',count,' time spent: ',time:0:3,' secs');
end;
begin
test1(100000);
test1(1000000);
test1(10000000);
test1(100000000);
end.
SerjeyMinsk, берите этот код и сохраняйте. Не как Unicode - как ASCII. И компилируйте FreePascal.
Вот результаты на моей машине:
Код:
Number of primes up to 100000 - 9592 time spent: 0.000 secs
Number of primes up to 1000000 - 78498 time spent: 0.156 secs
Number of primes up to 10000000 - 664579 time spent: 1.875 secs
Number of primes up to 100000000 - 5761455 time spent: 24.703 secs
У меня процессор загружен параллельно работающими приложениями, поэтому никакой чистоты эксперимента нет - данные годятся лишь для оценки порядка затрат времени.
-- 23:47 30.08.2009 --Да, есть еще такая штука, как решето Аткина-Бернштейна (2003). Авторы утверждают, что с его помощью за 19.6 секунд просеяли все простые до 10^9 на машине с процессором
UltraSPARC-I (167 MHz). Впрочем, они писали на Си, а он куда шустрее Pascal при работе с массивами.
. В каком диапазоне генерируются простые числа?
