2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21 ... 46  След.
 
 Re: Поиск простых чисел
Сообщение18.11.2009, 00:58 
Xaositect в сообщении #263089 писал(а):
Спасибо!

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

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

 
 
 
 Re: Поиск простых чисел
Сообщение06.01.2010, 22:17 
Аватара пользователя
Очень медленно. Хотя возможно, что у вас тормозит именно вывод в файла. Сколько времени занимает проверка, если отключить вывод в файл?

 
 
 
 Re: Поиск простых чисел
Сообщение06.01.2010, 22:43 
спасибо, огорчили. время не меняется

 
 
 
 Re: Поиск простых чисел
Сообщение06.01.2010, 22:58 
Аватара пользователя
Не огорчайтесь, многое зависит от выбранного языка программирования. Для какого-нибудь Python 36 секунд могут быть вполне пристойным временем.

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

 
 
 
 Re: Поиск простых чисел
Сообщение07.01.2010, 06:48 
]
Цитата:
Насчет алгоритма с 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.$$

 
 
 
 Re: Поиск простых чисел
Сообщение07.01.2010, 16:26 
Аватара пользователя
Руст в сообщении #278163 писал(а):
Этот вопрос здесь уже обсуждался.

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

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 00:01 
а какая временная зависимость при проверке чисел на простоту путем перебора. к сожалению здесь нет возможности разместить картинку. у меня получилась линейная зависимость (в среднем). при проверке от 1 до 1 000 000 000 с увеличением времени в пять раз. насколько это характерно для работы алгоритма такого типа?

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 00:24 
Аватара пользователя
mag_spb в сообщении #278685 писал(а):
а какая временная зависимость при проверке чисел на простоту путем перебора. к сожалению здесь нет возможности разместить картинку. у меня получилась линейная зависимость (в среднем). при проверке от 1 до 1 000 000 000 с увеличением времени в пять раз.

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

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

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 00:38 
зависимость времени работы алгоритма от величины проверяемого числа. алгоритм "тупого" перебора. что тут предъявлять?!...

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 00:54 
Аватара пользователя
Для проверки на простоту отдельно взятого числа $n$ достаточно $O(\pi(\sqrt n))=O({\sqrt n\over \ln n})$ операций. Так что линейной зависимостью тут и не пахнет.

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

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 13:46 
Изображение

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


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


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

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

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

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 14:40 
одна точка этого графика это время затраченное на проверку 1 000 000 чисел

 
 
 
 Re: Поиск простых чисел
Сообщение09.01.2010, 15:13 
Аватара пользователя
mag_spb в сообщении #278857 писал(а):
одна точка этого графика это время затраченное на проверку 1 000 000 чисел

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

 
 
 [ Сообщений: 682 ]  На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21 ... 46  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group