Есть такой вот алгоритм вывода списка простых чисел от 1 до 100.

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

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

есть более качественный алгоритм

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

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

> Вопрос: На чем ты пишеш?
На Глаголе.

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

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


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

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

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

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

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

Добавлено @ 10:12
Akina,

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

Это сообщение отредактировал(а) Дрон - 17.2.2006, 10:13

Спасибо.

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

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

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

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

Это сообщение отредактировал(а) Innuendo - 17.2.2006, 15:30

see above


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

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

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

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

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

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

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

Это сообщение отредактировал(а) Сый - 17.2.2006, 22:26

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

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

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

Провел тестирование алгоритма,
вот результаты:


[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 на число.

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

Это сообщение отредактировал(а) mes - 1.3.2006, 03:40