програма которая виводит все простие числа от 1 до 1000000 до 1сек

[PAWLO1993]

Мне нужна програма которая виводит все простие числа от 1 до 1000000 до 1сек.

[puffin]

function isPrime(X: word): boolean;
         var
            i: LongInt;
         Begin
                isPrime:=false;
                for i:=2 to trunc(sqrt(x)) do
                        if x mod i = 0 then Exit;
                isPrime:=true;
         End;

Вроде бы...

А вообще, используй google.ru. По-любому что-то да найдется.

[(: SyLvEsTeR :)]

Ya dumayu dla novi4kov etu proqrammu mojno bolee leq4e i ponatnee napisat...
vot tak ya dumayu doljda rabotat..

uses crt;
var
i,j:longint;
k:integer;
begin
While i<=1000000 do
begin
k:=0;j:=1;
while j<=i do
begin
if i mod j=0 then
inc(k);
inc(j);
end;
if k=2 then
write(i);
inc(i);
end;
end.

Ya dumayu alqoritm ponaten... yesi budut trudnosti ,moqu obyasnit)))

[PAWLO1993]

Програму и я сам могу легко написать, но мне нужно, щтоби она считала до 1секунды.

[alexBlack]

До миллиона простые числа просеиваются очень быстро.
Нужна небольшая оптимизация.
- Проверка делителей до sqrt(x), т.е. max до 1000. Кроме того нужно проверять не все числа подряд (в качестве делителей), а только простые. До 1000 их всего 168, причем сгенерировать их можно по ходу цикла.
- ну и пропускать четные.

С такой оптимизацией (реализовано в Delphi) - 250мс
...
Ради любопытства проверил без оптимизации - простой перебор всех делителей - чуть больше секунды.

[Карась]

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

До миллиона простые числа просеиваются очень быстро.
Нужна небольшая оптимизация.
- Проверка делителей до sqrt(x), т.е. max до 1000. Кроме того нужно проверять не все числа подряд (в качестве делителей), а только простые. До 1000 их всего 168, причем сгенерировать их можно по ходу цикла.
- ну и пропускать четные.

С такой оптимизацией (реализовано в Delphi) - 250мс
...
Ради любопытства проверил без оптимизации - простой перебор всех делителей - чуть больше секунды.

А каким образом были получены данные о скорости алгоритма ?
Можете код выложить?

А то мои ковыряния с GetTime ничево хорошего недали... Хотя это дело времени

[alexBlack]

Просто разница в значениях getTickCount:

var prime : array [1..100000] of integer;
var C:integer;

procedure TForm1.Button1Click(Sender: TObject);
var N, k, m, i, T:integer;
    b:boolean;
    F:textFile;
begin
   T := getTickCount;
   C := 0;
   // 1 - не является простым числом
   // 2 - единственное четное простое число
   inc(C); prime[C] := 2;

   N := 3;
   while N < 1000000 do begin
      k := trunc(sqrt(N));

      m := 2;  // деление на 2 не проверяем
      b := true;
      while m <= C do begin
         if prime[m] > k then break;
         if N mod prime[m] = 0 then begin
            b := false;
            break;
         end;
         inc(m);
      end;

      if b then begin
         inc(C);
         prime[C] := N;
      end;

      inc(N, 2);
   end;
   T := getTickCount - T;
   memo1.Lines.add('time = '+intToStr(T));

   assignFile(F, 'prime.txt'); rewrite(f);
   for i:=1 to C do begin
      writeLn(F, prime[i]);
   end;
   closeFile(F);
   {
   for i:=1 to C do begin
      memo1.lines.Add( intToStr(prime[i]) );
      if i mod 1000 = 0 then Application.processMessages;
   end;
   }
   memo1.Lines.add('count = '+intToStr(C));
end;

[RAVAL))]

Самый быстрый способ нахождения простых чисел это "Решето Эратосфена"

 VAR
  A,P      : Array[1..1000000] of Longint;
  i,j,k,lp : Longint;
BEGIN
  Assign(Output,'Out.txt'); Rewrite(Output);
  lp:=1;
  P[1]:=2;
  k:=0;
  For i:=3 to 1000000 Do Begin
    If Odd(i)
      Then Begin Inc(k); A[k]:=i; End;
  End;
  For i:=1 to k Do Begin
    If a[i]=0 Then Continue;
    Inc(lp);
    P[lp]:=A[i];
    j:=i+P[lp];
    While (j<=k) Do Begin
      A[j]:=0;
      Inc(j,P[lp]);
    End;
  End;
  For i:=1 to lp Do WriteLn(P[i]);
  Close(Output);
END.