Информация для пользователей Паскаля: загрузите PRIME4PA и изучите строки с 11 по 32.
/* Copyright (c) 1990, Borland International */
#include
prime(int n)
{
int i;
if (n % 2 == 0)
return (n==2);
if (n % 3 == 0)
return (n==3);
if (n % 5 == 0)
return (n==5);
for (i=7; i*i <= n; i+=2)
if (n % i == 0)
return 0;
return 1;
}
main()
{
int i, n;
n = 1000;
for (i=2; i<=n; i++)
if (prime(i))
printf(«%d\n», i);
}
{ Copyright (c) 1990, Borland International }
program Prime4PA;
Var
I,N: Integer;
Function Prime(N: Integer):Boolean;
Var
I: integer;
Begin
If (N MOD 2 = 0) then
Begin
Prime:= N = 2;
Exit;
End;
If (N MOD 3 = 0) then
Begin
Prime:= N = 3;
Exit;
End;
If (N MOD 5 = 0) then
Begin
Prime:= N = 5;
Exit;
End;
For I:= 7 to N-1 do
If (N MOD I = 0) then
Begin
Prime:= False;
Exit;
End;
Prime:= True;
End;
Begin
N:= 1000;
For I:= 2 to N do
If Prime(I) then
Writeln(I);
End.
В этих строках содержится ряд улучшений.
* Три оператора if в подпрограмме prime удаляют из рассмотрения числа, кратные 2, 3, и 5 соответственно. Если на основании этих проверок Вам не удается отсеять рассматриваемое число n, то приходится проверять его делимость на оставшиеся целые числа вплоть до корня квадратного из n. Начать эти проверки можно с числа 7, так как наличие операторов if исключает из рассмотрения все меньшие числа.
* Цикл for теперь работает с шагом 2, так как нет смысла рассматривать четные числа.
* Проверка i*i<=n заменила более дорогой, с точки зрения временных затрат, тест, основывающийся на вычислении квадратного корня.
Результатом всех этих изменений явилось то, что общее время выполнения уменьшилось более чем на одну секунду. Данные, приведенные на рисунке 1.7 показывают, что функция printf отнимает теперь 96 % всего времени выполнения.
Рис. 1.7 Временная и количественная статистика, PRIME4.
Сокращение времени ввода/вывода.
Изменение в доле времени, потребляемой оператором printf, говорит о том, что теперь быстродействие программы в большей степени ограничивается операторами ввода/вывода, чем ее вычислительной частью. Возможно, такое положение является вполне приемлемым. Но, хотя бы просто ради интереса, давайте попробуем выжать еще что-нибудь из этих операторов.
Загрузите PRIME5 в окно Module (Модуль) и посмотрите на 28 строку (строку 3 в Паскалевском варианте).
В Turbo C имеется более быстрый вариант функции printf, называемый cprintf, использование которого является единственным отличием программы PRIME5 от PRIME4. Функция cprintf обрабатывает ситуацию перехода на новую строку иначе, чем printf: в cprintf вместо единственного символа «новая строка» используется пара символов «возврат каретки»/«перевод строки» (\r \n).
