процедура.

[whatever]

Сообщение от BDA

"Выпендрился"

Кто бы говорил, у самого код частично на ассемблере Впрочем ТС не уточнял, на каком языке ему надо, так что имеешь право

P.S. Кстати, что за ассемблер? Хотелось бы документацию почитать, разобраться, как процедура работает.

[Hacker19_90]

Дальше за целой частью квадратного корня исследуемого числа бежать нет смыла, т.к. это точка симметрии делителей.Дальше за целой частью квадратного корня исследуемого числа бежать нет смыла, т.к. это точка симметрии делителей.

спс! возьму на заметку! +1

[Valio]

Сообщение от whatever

P.S. Кстати, что за ассемблер? Хотелось бы документацию почитать, разобраться, как процедура работает.

Эээээ.. это асм вставки в Делфи.

[s-andriano]

Ужасно неоптимальные алгоритмы.
Все простые числа в диапазоне принято искать решетом Эратосфена.

[SNUPY]

Ну вообще можно еще более оптимальнее сделать не гонять все от 1 до trunc(sqrt(j)). А гонять гонять только величины до этого найденных простых чисел с условием конца в trunc(<простое число>). но при это придется держать массив и к нему обращаться. Почему-то на прогоне до 100000 я особой скорости от этого не почуствовал (наверно виновно в этом обращение в память).

Сообщение от s-andriano

Ужасно неоптимальные алгоритмы.
Все простые числа в диапазоне принято искать решетом Эратосфена.

виноват походу вы об этом как раз и сказали =)

[Serge_Bliznykov]

Все простые числа в диапазоне принято искать решетом Эратосфена.

формально - да.
Но решение "в лоб" тоже достаточно эффективное!
Да и диапазон от 0 до 255 не такой огромный, чтобы огород городить...

так, развлечения ради...

function isPrime(X: LongInt): boolean;
var i: integer;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;


var
 i, Kol : LongInt;
 PrimeArr : array[1..10000] of Integer;

 {для подсчёта тиков}
 Ticks      : LongInt  absolute 0:$46c;
 OldTick    : LongInt;


begin
  OldTick := Ticks;
  Kol := 0;
  for i:=1 to 100000  do
      if isPrime(i) then begin
         inc(kol);
         PrimeArr[ kol ] := i;
      end;

  WriteLn('Матрица заполнена за ', Ticks - OldTick, ' тиков.');

  WriteLn('Всего найдено ',Kol,' простых чисел ');
  Readln
end.

на моём стареньком компьютере AMD 1.8 Ггц, под DOS в Windows XP, программа на турбопаскале обработала диапазон от 1 до 100000 за 3 тика (напоминаю, что в 1 секунде примерно 18.2 тиков таймера DOS) т.е.~ 0.1648 секунды... при этом найдено 9592 простых числа...

[s-andriano]

Сообщение от Serge_Bliznykov

формально - да.
Но решение "в лоб" тоже достаточно эффективное!
Да и диапазон от 0 до 255 не такой огромный, чтобы огород городить...
...
на моём стареньком компьютере AMD 1.8 Ггц, под DOS в Windows XP, программа на турбопаскале обработала диапазон от 1 до 100000 за 3 тика (напоминаю, что в 1 секунде примерно 18.2 тиков таймера DOS) т.е.~ 0.1648 секунды... при этом найдено 9592 простых числа...

Оно может быть эффективным в одном единственном случае - когда диапазон ограничен единственным числом (максимум, единицами).
Но для указанного диапазона разницу на глаз, естественно, не заметишь.
Когда-то давно, еще во времена существования Фидо, сравнивали решето Эратосфена с подобным алгоритмом для 16-разрядных чисел (т.е. до 65535). "Решето" оказалось быстрее более чем в 4000 раз. Измерить время выполнения в "тиках", естественно, было невозможно, поэтому "решето" загонялось внутрь цикла в 10000 проходов (ну а процессоры тогда были порядка 100 МГц).

Если требуется найти простые числа в большем диапазоне (например, до 2^32), алгоритм IMHO должен быть следующим:
1. Находим простые числа в диапазоне до 2^16, проверяя на ВСЕ делители до sqrt(N).
2. При нахождении за пределами этого диапазона в качестве делителей берем числа, найденные на этапе 1.

[Serge_Bliznykov]

Сообщение от s-andriano

Когда-то давно, еще во времена существования Фидо, сравнивали решето Эратосфена с

я где-то намекнул, что решето хуже прямого перебора?! Вы меня неправильно поняли - я сказал, что тут и прямого перебора более чем за глаза достаточно!

Сообщение от s-andriano

Измерить время выполнения в "тиках", естественно, было невозможно, поэтому "решето" загонялось внутрь цикла в 10000 проходов

ну да, решетом данная (исходная) задача решится за 0.0000001 секунды, а прямым перебором - 0.0004 с (цифры АБСОЛЮТНО УСЛОВНО-АБСТРАКТНЫЕ). Согласен, для учебной задачи это недопустимо долго!

Если требуется найти простые числа в большем диапазоне (например, до 2^32), алгоритм IMHO должен быть следующим:

согласен.
А Вы уверены, что автору темы эта информация будет полезна?

[s-andriano]

Сообщение от Serge_Bliznykov

А Вы уверены, что автору темы эта информация будет полезна?

К сожалению, не уверен. Но искренне надеюсь на это.

[ACE Valery]

А Вы уверены, что автору темы эта информация будет полезна?

Автору - вряд ли Не сомневаюсь, что он воспользовался первым ответом и забыл про тему. А вот мне было любопытно посмотреть. Спасибо всем