Как быстро найти простые числа?

[SASFM]

Здравствуйте ребята. Помогите пожалуйста с поиском простых чисел (2,3,5,7,11,13,17,19...)

[Plague]

В чем заключается Ваша проблема?

[SASFM]

Нужно найти 10000 простых цифры

[Dekay]

По закону распределения простых чисел ищите границу.
А потом запускаете решето Эратосфена (линейное)
Или сразу в решето кинуть большую верхнюю границу

[Аватар]

массив констант в программе с простыми числами. Самый быстрый способ

[FPaul]

Поиск простого числа с номером 1'000'000. Переделайте под себя.
Это FreePascal

{
Печать 1000000-го простого числа
}

{$BITPACKING ON}
program Eratosfen;

const
  //номер искомого простого числа
  NPrime = 1000 * 1000;
  //верхняя граница рассматриваемых кандидатов в простые числа
  Nmax = round(1.2 * NPrime * ln(NPrime));
type
  TVector = packed array [2..Nmax] of boolean;
var
  PrimeCandidate, Step, j, Count: QWord;
  Sieve: TVector;
begin
  (*
  PrimeCandidate := 2;
  while PrimeCandidate <= Nmax do
  begin
    Sieve[PrimeCandidate] := True;
    Inc(PrimeCandidate);
  end;
  *)
  fillchar(Sieve, sizeof(Sieve), $FF);

  Count := 0;
  PrimeCandidate := 2;
  Step  := 2;
  while (PrimeCandidate <= Nmax) do
  begin
    if Sieve[PrimeCandidate] then
    begin
      j := PrimeCandidate;
      while (Nmax - PrimeCandidate >= j) do
      begin
        j := j + PrimeCandidate;
        Sieve[j] := False;
      end;

      Inc(Count);
      if Count = NPrime then
        break;

    end;

    case PrimeCandidate of
      2: PrimeCandidate := 3;
      3: PrimeCandidate := 5;
      else
      begin
        PrimeCandidate := PrimeCandidate + Step;
        Step := Step xor $6;
      end
    end;

  end;

  writeln('Max prime candidate = ', Nmax);
  writeln('Last prime = ', PrimeCandidate);
  writeln('Count = ', Count);
end.

[gromdel]

А как такое решение, подойдет?

var
i,j,a,c:integer;
begin
for i:=1 to 1000 do begin
c:=0;
   for j:=1 to i do begin
  a:=i mod j;
  if i mod j=0 then inc(c);
 end;
  if c=2 then writeln(i);
 
  end;
  end.

[Serge_Bliznykov]

gromdel, нет.

во-первых, это КРАЙНЕ неэффективно (вы посчитайте, сколько делителей у числа 900, например), зачем крутить цикл, если уже понятно, что число не простое, зачем цикл до i, когда все делители расположены до sqrt(i) и т.д.

во-вторых, нужно найти 10000 простых чисел, а не найти простые числа в диапазоне от 1 до 1000! Разницу улавливаете? Вот Ваш код сколько простых чисел найдёт?
явно меньше 300

[gromdel]

дошло. 10000 простых чисел. а я до 10000 %)

[type_Oleg]

Сообщение от Аватар

массив констант в программе с простыми числами. Самый быстрый способ

Только антивирус отключить предварительно.