Большие числа

[Лекс Айрин]

Судя по всему, у тебя съедает время цикл for предлагаю на время забыть о его существовании. Ну и подумать об обходе уже вычеркнутых позиций. Ах да, не понял почему массив не булевый во втором примере... Ведь его индекс можно использовать как число. И с помощью false отмечать отвергнутые числа.

Добавлено спустя 15 минут 37 секунд:
В первом примере, где у тебя лимит времени чуть больше секунды, печатай найденные простые числа сразу, а не в отдельном цикле. Тебе же нет смысла их хранить, а просто вывести на экран.

[Evgen]

Лекс Айрин мне числа не надо печатать, мне надо подсчитать их количество. В таблице S я на место непростых ставлю нули и потом подсчитываю единицы

[Vadim]

Evgen
Вот здесь тоже решето Эратосфена, попробуйте его:
http://num-anal.srcc.msu.ru/lib_na/cat/ ... a12i_p.htm
Там по у словию как раз Ваша задача - найти все простые не превышающие по значению определённое число. Предварительно вычисляется возможный объём массива хранилища.

Добавлено спустя 6 минут 38 секунд:
Забыл сказать. Там перевод алгоритма из Фортрана в Паскаль, поэтому присутствуют GOTO. Если это нежелательно, то вот мой перевод этой функции на современный Паскаль:

Код: Выделить всё

// Входные параметры:
//   - N - предельное значение до которого ищутся простые числа;
//   - IP - масств, куда помещаются простые числа.
procedure PA12I(N : Integer; var IP : Array of Integer);
var
  I,J,K : Integer;
  S : Double;

begin
  IP[0] := 1;
  IP[1] := 2;
  IP[2] := 3;
  
  if ( N > 3 ) then
  begin
    K := 3;
    J := 3;
    while ( K<=N ) do
    begin
      I := 2;
      S := Sqrt(K);
      While 1=1 Do
      Begin
        Inc(I);
        if ( IP[I-1] > S ) then 
        begin
          IP[J-1] := K;
          Inc(J);
          Break;          
        end
        Else
          if ( K div IP[I-1]*IP[I-1] <> K ) then 
            Continue
          else
            Break;
      end;
    inc(K,2);
    end;
    
  end;
end;

[Evgen]

Vadim, спасибо завтра попробую, то есть сегодня. Йду спать (у нас 3.22 ночи)

[Лекс Айрин]

Evgen, так и считай сразу, так даже проще, чем записывая в гигантский массив, а потом его перелопачивать заново.

[iskander]

но постараюсь реализовать алгоритм Iskandera

Evgen, вы это о чем? Ну, хорошо, так и быть.
Насколько я понял, Дож предлагает выполнить то что описал в один проход.
Я предлагаю самую чуточку попроще.
Для начала вам нужно подумать, как модифицировать решето Эратосфена,
чтобы имея список простых чисел от 2 до Sqrt(B), можно было начинать
вычеркивать составные числа начиная с произвольного наперед заданного числа.
Ну и соответственно сначала с помощью обычного решета получаете список простых чисел,
затем во втором проходе применяете модифицированный алгоритм.

Вадим, чот этот PA12I удобен как штаны с ширинкой сзади.
Сначала посчитать примерную длину массива,
заполнить его каким-то сигнальным значением,
выполнить процедуру,
пройти еще раз по массиву и посчитать количество элементов,
усечь массив, если нужно.
Предлагаю более удобный вариант:

Код: Выделить всё

type
  TIntArray = array of Integer;

function PrimeSieve(UpBound: Integer): TIntArray;
var
  IsPrime: array of Boolean = nil;
  I, Count: Integer;
  J: Int64;
begin
  if UpBound < 2 then
    exit(nil);
  SetLength(IsPrime, UpBound + 1);
  for I := 0 to High(IsPrime) do
    IsPrime[I] := True;
  Count := 0;
  for I := 2 to High(IsPrime) do
    if IsPrime[I] then
      begin
        Inc(Count);
        J := Int64(I) * Int64(I);
        while J <= UpBound do
          begin
            IsPrime[J] := False;
            Inc(J, I);
          end;
      end;
  SetLength(Result, Count);
  J := 0;
  for I := 2 to High(IsPrime) do
    if IsPrime[I] then
      begin
        Result[J] := I;
        Inc(J);
      end;
end;  

По скорости постараюсь вечером сравнить.

[Vadim]

чот этот PA12I удобен как штаны с ширинкой сзади.

Там задача несколько другая, нежели выявить простые числа до какого-то значения. Нужно эти простые числа сохранить для дальнейшего использования.

заполнить его каким-то сигнальным значением,

Уже не надо. Там был старый Паскаль. В нынешнем по умолчанию нолики будут...
С размером хранилища да, согласен, формула расчёта даёт значение намного превосходящую реальную потребность. Но есть и другие, более современные формулы...
В принципе, если нужно только количество, то массив вообще не нужен. Если число найдено - Inc(Count)...

[iskander]

Уже не надо. Там был старый Паскаль. В нынешнем по умолчанию нолики будут...

Откуда инфа?

[Vadim]

Откуда инфа?

"... И опыт, сын ошибок трудных..."
Инфа только из личного опыта. Хотя может у разрабов тоже что-то написано. Можно проверить такой штукой:

Код: Выделить всё

program p1;

procedure prc;
Var
  i: integer;
  d: double;
Begin
  WriteLn(i);
  WriteLn(d:10:3);
end;

begin
  prc;
end.

У целочисленной переменной будет мусор, а вот у плавающей запятой именно ноль.

[iskander]

Спасибо.

[Дож]

Код: Выделить всё

program p1;

procedure FillGarbage;
Var
  i: integer;
  d: double;
Begin
  i := 666;
  d := 666;
end;

procedure prc;
Var
  i: integer;
  d: double;
Begin
  WriteLn(i);
  WriteLn(d:10:3);
end;

begin
  FillGarbage;
  prc;
end.

[Vadim]

Дож
Резонно. Но во всех предыдущих случаях наличие доп. процедур не предусматривалось. В Вашем случае действительно, без инициализации никак не обойтись.

[Дож]

Омг...

[xdsl]

Мне только одно непонятно, как вводить число N? Это явный стёб со стороны препода.
Сразу представляю такой диалог:
Студент:
- Фигня задача, простой перебор ...
Преподаватель:
- Фигня, говоришь ... Вот тебе N = 10^10000, иди перебирай, надоест - приходи, поговорим.

А задача - математическая, циклов тут не надо.

[Alex2013]

По моему это чисто математический трюк то есть идет счетчик коробок то 1 до N нужно как то ЗАРАНЕЕ вычислить сколько номеров будет содержать число 4 .... или какие не будут его содержать !
Зы
Но перебором тоже решается (это же чистый числовой бутфорс ! я и с буквами такой делал водил БИНАРНОЕ число "нужной разрядности" (примерно 10+(33+26)*2 +спец символы) и крутил чисто "по счетчику" пробегая все возможные значения ).... а тут еще проще делается тройной четверной или столько там нужно цикл числа счетчиков умножается на разряд и собираются в строку причем чем при появлении четверки сборка останавливается (кстати можно в вообще не сохранять строку она же не нужна ) ... Можно сделать один цикл через while ... Вообщем можно, но думать в всерьез лень. (Правда есть загвоздка со временем тут я просто заранее предсказать не могу. )