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

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

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

Сообщение Лекс Айрин » 20.01.2019 02:37:21

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

Добавлено спустя 15 минут 37 секунд:
В первом примере, где у тебя лимит времени чуть больше секунды, печатай найденные простые числа сразу, а не в отдельном цикле. Тебе же нет смысла их хранить, а просто вывести на экран.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

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

Сообщение Evgen » 20.01.2019 04:18:23

Лекс Айрин мне числа не надо печатать, мне надо подсчитать их количество. В таблице S я на место непростых ставлю нули и потом подсчитываю единицы
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение Vadim » 20.01.2019 04:29:28

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;
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

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

Сообщение Evgen » 20.01.2019 05:23:43

Vadim, спасибо завтра попробую, то есть сегодня. Йду спать (у нас 3.22 ночи)
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение Лекс Айрин » 20.01.2019 08:19:09

Evgen, так и считай сразу, так даже проще, чем записывая в гигантский массив, а потом его перелопачивать заново.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

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

Сообщение iskander » 20.01.2019 14:30:49

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

Evgen, вы это о чем? Ну, хорошо, так и быть. :wink:
Насколько я понял, Дож предлагает выполнить то что описал в один проход.
Я предлагаю самую чуточку попроще.
Для начала вам нужно подумать, как модифицировать решето Эратосфена,
чтобы имея список простых чисел от 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; 

По скорости постараюсь вечером сравнить.
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение Vadim » 20.01.2019 14:40:15

iskander писал(а): чот этот PA12I удобен как штаны с ширинкой сзади.

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

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

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

Сообщение iskander » 07.02.2019 09:28:17

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

Откуда инфа?
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение Vadim » 07.02.2019 09:52:10

iskander писал(а):Откуда инфа?

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

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

begin
  prc;
end.

У целочисленной переменной будет мусор, а вот у плавающей запятой именно ноль.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

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

Сообщение iskander » 07.02.2019 10:34:26

Спасибо.
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение Дож » 07.02.2019 10:39:46

Код: Выделить всё
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.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение Vadim » 07.02.2019 11:26:44

Дож
Резонно. Но во всех предыдущих случаях наличие доп. процедур не предусматривалось. В Вашем случае действительно, без инициализации никак не обойтись.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

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

Сообщение Дож » 07.02.2019 11:36:47

Омг...
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение xdsl » 10.04.2019 13:40:33

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

А задача - математическая, циклов тут не надо.
xdsl
постоялец
 
Сообщения: 131
Зарегистрирован: 15.01.2009 13:49:03

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

Сообщение Alex2013 » 10.04.2019 15:17:22

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

Пред.След.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 43

Рейтинг@Mail.ru