Login
Поиск простого числа
262 просмотров
Перейти к просмотру всей ветки
scorpi_ скептик
in Antwort barmaglot 08.11.06 12:04, Zuletzt geändert 08.11.06 19:54 (scorpi_)
Итого:: если бы песня про четыре порядка была правильной, то решето в этом случае потребовало бы меньше, чем 1312 вычёркиваний.
Гыыыыы, извини, ты о теории сложности хоть какое-нибудь представление имеешь? Решето это O(n*log n), а твой алгоритм O(n^2), поэтому коэффициенты (которые весьма не в твою пользу, ибо в решете сплошь однотактовые операции, а у тебя дорогостоящее деление) считать излишне.
PS Сорри, не заметил ограничения по корням. Тогда O(n^1.5) - всё равно хуже чем O(n*log n).
PPS Я писал о числах, влезающих в интеджер, т. е. до порядка 32 тысяч. - всё ещё на 8086 сидишь?
Бедненьий... У меня так интеджер 64-битовый
Гыыыыы, извини, ты о теории сложности хоть какое-нибудь представление имеешь? Решето это O(n*log n), а твой алгоритм O(n^2), поэтому коэффициенты (которые весьма не в твою пользу, ибо в решете сплошь однотактовые операции, а у тебя дорогостоящее деление) считать излишне.
PS Сорри, не заметил ограничения по корням. Тогда O(n^1.5) - всё равно хуже чем O(n*log n).
PPS Я писал о числах, влезающих в интеджер, т. е. до порядка 32 тысяч. - всё ещё на 8086 сидишь?
Бедненьий... У меня так интеджер 64-битовый