Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 29.11.2016, 18:10   #1
SASFM
Форумчанин
 
Аватар для SASFM
 
Регистрация: 26.03.2015
Сообщений: 191
Вопрос Как быстро найти простые числа?

Здравствуйте ребята. Помогите пожалуйста с поиском простых чисел (2,3,5,7,11,13,17,19...)
Моя родина там, где мой компьютер
SASFM вне форума Ответить с цитированием
Старый 29.11.2016, 18:21   #2
Plague
Забанен
Форумчанин Подтвердите свой е-майл
 
Аватар для Plague
 
Регистрация: 01.11.2006
Сообщений: 420
По умолчанию

В чем заключается Ваша проблема?
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума Ответить с цитированием
Старый 29.11.2016, 19:02   #3
SASFM
Форумчанин
 
Аватар для SASFM
 
Регистрация: 26.03.2015
Сообщений: 191
По умолчанию

Нужно найти 10000 простых цифры
Моя родина там, где мой компьютер
SASFM вне форума Ответить с цитированием
Старый 29.11.2016, 19:20   #4
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

По закону распределения простых чисел ищите границу.
А потом запускаете решето Эратосфена (линейное)
Или сразу в решето кинуть большую верхнюю границу
Dekay вне форума Ответить с цитированием
Старый 29.11.2016, 19:26   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

массив констант в программе с простыми числами. Самый быстрый способ
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 29.11.2016, 19:30   #6
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

Поиск простого числа с номером 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.
FPaul вне форума Ответить с цитированием
Старый 29.11.2016, 21:09   #7
gromdel
Пользователь
 
Регистрация: 24.04.2012
Сообщений: 68
По умолчанию

А как такое решение, подойдет?
Код:
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.
gromdel вне форума Ответить с цитированием
Старый 29.11.2016, 21:31   #8
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

gromdel, нет.

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

во-вторых, нужно найти 10000 простых чисел, а не найти простые числа в диапазоне от 1 до 1000! Разницу улавливаете? Вот Ваш код сколько простых чисел найдёт?
явно меньше 300
Serge_Bliznykov вне форума Ответить с цитированием
Старый 29.11.2016, 21:42   #9
gromdel
Пользователь
 
Регистрация: 24.04.2012
Сообщений: 68
По умолчанию

дошло. 10000 простых чисел. а я до 10000 %)
gromdel вне форума Ответить с цитированием
Старый 29.11.2016, 22:05   #10
type_Oleg
Старожил
 
Аватар для type_Oleg
 
Регистрация: 02.03.2008
Сообщений: 2,538
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
массив констант в программе с простыми числами. Самый быстрый способ
Только антивирус отключить предварительно.
type_Oleg вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
найти все простые делители числа н keyshia_nicole Visual C++ 0 31.01.2014 18:39
В массиве А(100) найти простые числа. olegk95 Помощь студентам 2 10.12.2013 09:56
Найти все простые числа С++ vsubotka Помощь студентам 3 20.11.2013 12:05
Задачи в ТурбоПаскаль: найти числа Армстронга и просуммировать числа в последовательности номера которых простые числа Lena1808 Помощь студентам 1 17.05.2012 08:00