Мой лучший друг-отладчик!
|
|
1 | |
Конкурс(поиск простых чисел)24.07.2012, 20:30. Показов 8554. Ответов 74
Метки нет (Все метки)
Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое!
Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю)
0
|
24.07.2012, 20:30 | |
Ответы с готовыми решениями:
74
Поиск простых чисел Поиск простых чисел Поиск простых чисел Поиск простых чисел |
Higher
|
|
31.07.2012, 17:06 | 62 |
Так в никсах консоль работает намного быстрее, чем в винде.
В любом случае, на рекорд тот код явно не потянет, т.к. алгоритм слишком наивен(примерно O(nlogn) с большой константой). У меня, к примеру, O(nloglogn) с гораздо меньшей константой. Причем с такими ограничениями это, наверное, оптимальный алгоритм, т.к. быстрее решета Эратосфена вроде как только решето Аткина, но у Аткина будет немного выше константа.
0
|
63 / 58 / 14
Регистрация: 14.12.2011
Сообщений: 193
|
|
31.07.2012, 17:16 | 64 |
Один и тот же код разные компиляторы компилируют по разному. Только что проверил в
GNU - время 1-2sec Borland - время ~ 2-3 sec VC++ - время >3 sec
0
|
5498 / 4893 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
|
|
31.07.2012, 18:42 | 65 |
И даже постоянно? Запускаю код в Code Blocks и смотрю, какое время выполнения программы он показывает. И в чём путаю?
Добавлено через 1 минуту Вы время компиляции проверяете? А я выполнения. Добавлено через 12 минут Нужно тогда договориться, как замер делать. С выводом, без вывода, на какой машине, с какой ОС, каким компилятором компилировать, с какими флагами и т.д.
0
|
63 / 58 / 14
Регистрация: 14.12.2011
Сообщений: 193
|
|
31.07.2012, 19:16 | 66 |
Кто Вам такое сказал? Я имел ввиду что, программы скомпилированые разными компиляторами, имеют разное время выполнения. Тот же Code::Blocks у меня 1.5с показывал.
Кажеться время тему закрывать, одно бла бла бла началось..
0
|
iSeva
|
|
21.11.2012, 20:30 | 68 |
Извиняюсь за вторжение.
У меня есть собственный алгоритм поиска простых чисел, который должен работать на порядки быстрее существующих. Проблема в том, что я на С++ не программировал с института. Написал прогу на флеше на AS. Можно выложить листинг на AS? |
Модератор
12454 / 7479 / 1752
Регистрация: 25.07.2009
Сообщений: 13,751
|
|
22.11.2012, 02:14 | 69 |
iSeva, только комментарии поподробнее напишите и описание алгоритма‚ а то заинтриговать получилось‚ но можете непонятым остаться.
0
|
iSeva
|
|
22.11.2012, 08:40 | 70 |
Немного поторописля с самим алгоритмом. Вчера отлаживал, есть глюки. Для затравки скажу найденное мной свойство простых чисел, на котором основан алгоритм. Любое нечетное число можно представить в виде разницы квадратов натуральных чисел. Пример 11=6^2-5^2 49=25^2-24^2. Причем как видно числа возводимые в квадрат соседние 6 и 5; 25 и 24. Это свойство справидливо для всех нечетных чисел. Если найдется еще одна пара чисел разница квадратов равна искомому числу, то исходное число не простое. 11 нельзя представить в виде разницы квадратов других чесел значит 11 простое, а вот 49=7^2-0^2. На этом свойсте и работает мой алгоритм. Надеюсь сегодня его допишу. Небольшая проблемы в оптимизаци поиска.
|
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 7
|
|
25.11.2012, 17:31 | 71 |
Не подскажете почему ваш код в файл выводит числа если задавать N больше 1000 выдает китайские иероглифы ?
0
|
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 7
|
|
25.11.2012, 17:53 | 73 |
0
|
bert_
|
||||||
27.08.2013, 10:51 | 75 | |||||
Добавлено через 17 минут до 10^8 в файл за 43 сек |
27.08.2013, 10:51 | |
27.08.2013, 10:51 | |
Помогаю со студенческими работами здесь
75
Поиск простых чисел Поиск простых чисел Поиск простых чисел Поиск простых чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |