Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Простые числа


Автор: Сый 16.2.2006, 22:40
Есть такой вот алгоритм вывода списка простых чисел от 1 до 100.
Код

ЗАДАЧА ВыводПростыхЧисел(); 
ПЕР 
Простое:КЛЮЧ; 
Число,Дел:ЦЕЛ; 
УКАЗ 
Число:=3; 
Вывод.ЧЦел("%d^%d^%d^",1,2,3,0); 
ПОВТОРЯТЬ 
  Простое:=ВКЛ; 
  УВЕЛИЧИТЬ(Число); 
  Дел:=3; 
  ЕСЛИ ЧЕТ(Число) ТО Простое:=ОТКЛ ИНАЧЕ 
    ПОВТОРЯТЬ 
      ЕСЛИ Число ОСТАТОК Дел = 0 ТО Простое := ОТКЛ КОН; 
      УВЕЛИЧИТЬ(Дел); 
    ДО Дел = Число; 
  КОН; 
  ЕСЛИ Простое ТО Вывод.ЧЦел("%d^",Число,0,0,0) КОН; 
ДО Число = 100. 
КОН ВыводПростыхЧисел;

Но это довольно медленный алгоритм. Нет ли более качественного способа вывода списка простых чисел?

Автор: Fin 16.2.2006, 23:26
Сый, Вопрос: На чем ты пишеш? Я сначало подумал, что это 1С:Бухгалтерия.

Автор: esperant0 16.2.2006, 23:46
есть более качественный алгоритм

в таблицу записываешь все простые числа от 1 до 100 они известны заранее

а потом просто распечатываешь таблицу в цикле

Автор: Сый 17.2.2006, 09:03
> Вопрос: На чем ты пишеш?
На Глаголе.

> в таблицу записываешь все простые числа от 1 до 100 они известны заранее
Это, конечно, удобно, но вдруг мне понадобится вывести числа в других интервалах?

Автор: Akina 17.2.2006, 10:09
Цитата(Сый @ 17.2.2006, 10:03 Найти цитируемый пост)
На Глаголе.

Завязывай с этой хренью и переходи на человеческий язык.

Цитата(Сый @ 17.2.2006, 10:03 Найти цитируемый пост)
вдруг мне понадобится вывести числа в других интервалах?

http://algolist.manual.ru/maths/teornum/gene_prime.php
Что же до генерации списка небольших (до миллиона там) - тривиальное решето Эратосфена или аналогичные простейшие методы.

Автор: Дрон 17.2.2006, 10:10
Сый,
я думаю, что если поискать в интернете, то найдёшь много более интересных алгоритмов.

Как минимум, я вижу, что ты проверяешь делимость на все числа до данного. А это уже не верно, достаточно проверять до корня квадратного из данного, потому что на после этого ты уже повторяешься.

Смотри, делители 20:

1 и 20
2 и 10
4 и 5
--- всё, дальше уже не надо, корень из 20 он между 4 и 5 находится
5 и 4
10 и 2
20 и 1

Добавлено @ 10:12
Akina,
Цитата(Akina @ 17.2.2006, 10:09 Найти цитируемый пост)

http://algolist.manual.ru/maths/teornum/gene_prime.php

Конечно, но мне кажется тут не масштабы smile

Автор: Сый 17.2.2006, 14:32
Спасибо.

> Завязывай с этой хренью и переходи на человеческий язык.
Чем же тебе так не нравится этот язык?

Автор: Innuendo 17.2.2006, 15:28
очень рациональный поиск простых чисел это решето этого (блин, забыл, ну кто и первый выявил эти простые числа).
берешь массив своих чисел (к примеру от 2 до 100 - 1 сразу выкидываешь)

и начинаешь делить от первого число на эти же числа.
То есть:
сначала делишь все числа на 2. Те что поделились без остатка выкидвыаешь из массива. Теперь массив состоит только из нечетных чисел.
потом делишь все на 3, те что поделились без остатка выкидвыаешь... Потом (так как 4 выкинуто) оно берет 5. Ну понятно, думаю.. принцип решета.
В итоге в этом же массиве остануться только простые числа.

Если правельно использовать циклы, то тут 5-6 строк получиться.. И самое главное что перебор сокращается до минимума!

Автор: Akina 17.2.2006, 16:38
Цитата(Innuendo @ 17.2.2006, 16:28 Найти цитируемый пост)
очень рациональный поиск простых чисел это решето этого (блин, забыл, ну кто и первый выявил эти простые числа).

see above smile

Цитата(Сый @ 17.2.2006, 15:32 Найти цитируемый пост)
Чем же тебе так не нравится этот язык?

Знаешь, когда верблюда спросили, почему у него спина кривая, он ответил - "А что у меня прямое?"...

Автор: SoWa 17.2.2006, 21:25
Цитата(Сый @ 17.2.2006, 14:32 Найти цитируемый пост)
Чем же тебе так не нравится этот язык?

Нечитабельно!!! Я пока разобрался, мозги сломал.
Пиши хоть на алголе, но лучше на Паскале или Си. Лучше не Паскале smile

А по вопросу- существует полином Мятисевича n-ой степени.
Он в помощь!

Автор: Fin 17.2.2006, 21:38
SoWa, Синтаксис это дело привычки. Я лично не хотел бы писать кирилицей. Только по одной причине. Это надо все время переключать кодировку клавиатуры. Так как, судя по листингу, есть символы, которые отсутствуют в раскладке кирилици. Я одно время так писал. Это сильно раздражает.
Добавлено @ 21:40
А сама форма построения программы очень сильно напоминает Паскаль.

Автор: Сый 17.2.2006, 22:23
> Нечитабельно!!! Я пока разобрался, мозги сломал.
По-моему, наоборот. Зависит от привычки...

>есть символы, которые отсутствуют в раскладке кирилици
Переключать раскладку приходится, хотя не очень часто. Однако, думаю, это не причина отказываться от этого языка. Эти же претензии можно предъявить и разработчикам данного типа клавиатуры.

> А сама форма построения программы очень сильно напоминает Паскаль.
Да, Глагол - язык, родственный языкам Паскаль и Оберон (подробнее см. документацию по языку на сайте http://glagol.nad.ru ).
Добавлено @ 22:37
Насчёт алгоримта - пожалуй, удовлетворюсь ограничением вычисления остатка до квадратного корня из числа, заменив ДО Дел = Число; на ДО Дел > УЗК(ВШИРЦЕЛ(УЗК(Матем.квкор(Число))));.
Всем спасибо.

Автор: III.nfo 17.2.2006, 23:04
Сый, посмотрите http://www.laplas.narod.ru/moiform.htm (http://www.laplas.narod.ru/moiform.htm) пункт 4.

Автор: mes 1.3.2006, 02:47
Вот код на Дельфи, если что не понятно будет спрашивай.
Етот код подходит если линейка чисел недлинная, потому что
1. Создаётся массив и предполагается, что все элементы = простые числа
2. Начиная с 2х идет перебор всех возможных множителей.
Естествено результат умножения будет составное число, поэтому, если ето число находится в диапазоне нужных нам чисел, отмечаем его в списке как составное.
3. Если не достигли максимально возможного множителя для наибольшего числа, то продолжаем перебор множителей с начала,(увеличив первый множитель)
Когда перебор множителей закончен, перебираем список
Если число отмечено как простое то печатаем.

Преимушества данного алгоритма ето отсутствие деления(так как очен медленная операция).
Недостатки - нахождение в памяти массива чисел.

Код

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils, Math;
const Max = 98;
      Min = 3;
Var Spisok: array [Min..Max] of boolean;
       mnozhitel1:integer=1;
       i,Mnozhitel2,res:integer;
       MaxDivMnozhitel, MaxDiv2:integer;

begin

  repeat  Inc(Mnozhitel1);

        MaxDivMnozhitel:= Max Div Mnozhitel1;
   for Mnozhitel2:=Mnozhitel1 to  MaxDivMnozhitel do
   begin
      res := Mnozhitel2* Mnozhitel1;
      if (res>=Min) and (res<=Max)
      then  Spisok[res] := True;
    end;

  Until  not(mnozhitel1<MaxdivMnozhitel);

  for i:=Min to Max do
  if Spisok[i]=False then write (i,' ,');

       sleep (2000);
end.

Автор: mes 1.3.2006, 03:32
Провел тестирование алгоритма,
вот результаты:


[font=impact]
[code=nocolor]



|..Длина цепочки..|..Кол-во операций ..|.. Кол-во операций .|..Кол-во простых.. |
|..... от 3 до...........|.... умножения .........|...... деления ............|..... чисел .............|
|.....10000000........|...... 71364264 ........ |....... 3161..................|.... 664578............|
|.....1000000..........|........ 5985518 ........ |......... 999 ................ |...... 78497............|
|......100000...........|.......... 483533 .........|......... 315 .................|........ 9591............|
|.........100..............|............ 143 ............ |........... 9...................|........... 24.............|





При мах=100 общее кол-во операций = 1.5 на число, из них только 9 делений.

При мах=10млн. общее кол-во операций = 8 на число.

Сам не ожидал такого результата smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)