Поиск простых чисел

[VAL]

Xaositect в сообщении #263089 писал(а):

http://en.wikipedia.org/wiki/FRACTRAN ?

Спасибо!

Если бы я не поленился пойти дальше по ссылке в статье википедии, ссылку на которую привел Droog_Andrey, не беспокоил бы людей почем зря

[mag_spb]

Доброго времени суток! Уважаемые сторожилы этого форуа хотелось бы узнать 36 сек. для проверки чисел на простоту в диапазоне от 100 000 000 до 101 000 000 и вывод их в текстовый файл на проце AMD3200+ 1,8ГГц это очень медленно?

[Бодигрим]

Очень медленно. Хотя возможно, что у вас тормозит именно вывод в файла. Сколько времени занимает проверка, если отключить вывод в файл?

[mag_spb]

спасибо, огорчили. время не меняется

[Бодигрим]

Не огорчайтесь, многое зависит от выбранного языка программирования. Для какого-нибудь Python 36 секунд могут быть вполне пристойным временем.

Выше по теме мы проводили замеры - за время порядка вашего компилируемая программа успевает найти все простые, меньшие 100 000 000.

[Руст]

]

Цитата:

Насчет алгоритма с 14-ю дробями. Мой склероз неумолимо прогрессирует и я уже забыл, откуда я его знаю (возможно, от maxal'а, но не уверен). Подскажите: Кто придумал? Когда? На чем основано доказательство (а может, его вовсе нет и после пары тыщ простых он собъется)? Существуют ли другие наборы рациональных чисел, приводящие к такому же эффекту? Как строить такие наборы? И т.д., и т.п., etc.

[/quote][/quote]
Этот вопрос здесь уже обсуждался. Я привел даже алгоритм с 9 числами

$$\frac 35 , \frac{67375}{108}, \frac{175}{18}, \frac{55}{39}, \frac 13 , \frac{26}{77}, \frac 67 , \frac{9}{13}, 189.$$

[maxal]

Руст в сообщении #278163 писал(а):

Этот вопрос здесь уже обсуждался.

А именно в этой теме: topic1440.html

[mag_spb]

а какая временная зависимость при проверке чисел на простоту путем перебора. к сожалению здесь нет возможности разместить картинку. у меня получилась линейная зависимость (в среднем). при проверке от 1 до 1 000 000 000 с увеличением времени в пять раз. насколько это характерно для работы алгоритма такого типа?

[Бодигрим]

mag_spb в сообщении #278685 писал(а):

а какая временная зависимость при проверке чисел на простоту путем перебора. к сожалению здесь нет возможности разместить картинку. у меня получилась линейная зависимость (в среднем). при проверке от 1 до 1 000 000 000 с увеличением времени в пять раз.

Зависимость между чем и чем? Между временем работы программы и ...?

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

[mag_spb]

зависимость времени работы алгоритма от величины проверяемого числа. алгоритм "тупого" перебора. что тут предъявлять?!...

[Бодигрим]

Для проверки на простоту отдельно взятого числа $n$ достаточно $O(\pi(\sqrt n))=O({\sqrt n\over \ln n})$ операций. Так что линейной зависимостью тут и не пахнет.

А тупой перебор разным бывает. Бывает совсем-совсем тупой, бывает не очень тупой, а бывает и почти не тупой. Вы как делители перебираете?

[mag_spb]

Цитата:

Цитата:

mag_spb в сообщении #278685 писал(а):
а какая временная зависимость при проверке чисел на простоту путем перебора. к сожалению здесь нет возможности разместить картинку. у меня получилась линейная зависимость (в среднем). при проверке от 1 до 1 000 000 000 с увеличением времени в пять раз.

Зависимость между чем и чем? Между временем работы программы и ...?

график зависимости времени работы алгоритма от величины проверяемого числа (от 1 до 1 000 000 000)

[Бодигрим]

Ну, график $\sqrt{n}/\ln n$ тоже для неискушенного взгляда несколько смахивает на линейную функцию. Ваш график не очень представителен - во-первых, вы его ведь строили не по миллиарду точек, а только по некоторым из них; во-вторых, какая у вас погрешность определения времени в программе?

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

[mag_spb]

одна точка этого графика это время затраченное на проверку 1 000 000 чисел

[Бодигрим]

mag_spb в сообщении #278857 писал(а):

одна точка этого графика это время затраченное на проверку 1 000 000 чисел

Так бы сразу и сказали. Хотя теперь резкие пики на графике смотрятся еще более странно - или это результат загрузки процессора другими процессами? Код показывать отказываетесь?