|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
17.03.2018, 00:12 | #1 |
Пользователь
Регистрация: 12.03.2018
Сообщений: 11
|
Нужно найти 2 последних простых числа, от 5 до n. 5<=n<10^9. За 0.1сек.
У меня тут проблемка. Весь код написан, а я должен написать только функцию которая будет находить 2 последних простых числа, от 5 до n.
Пробовал с помощью Решето Эратосфена, и сделать array[10^9], был слишком большой, мне пишет что максимум можно сделать 10^8 . Подумал что пусть хотяб так, тоже норм должно быть. хотя 50% будет решено. Но 9/10 ответов не верны и 1/10 просто превышен лимит времени. Допустим дано n=28. тогда a=23 . b=19. Код:
|
17.03.2018, 00:26 | #2 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,331
|
Для хранения 0 и 1 достаточно 1 бита, у вас же в массиве tab 0/1 хранятся в 64 битах! Одними только битовыми операциями, прочих равных, емкость массива увеличится в 64 раза!
|
17.03.2018, 00:39 | #3 |
Пользователь
Регистрация: 12.03.2018
Сообщений: 11
|
В кодблоке ошибок вроде бы нету. можно создавать bool [10^9]. а вот на сайте с тестом даёт ошибку с памятью. я превысил лимит памяти типо. caught fatal signal 11
---------------- немного улучшил(но это не точно) код, и всё равно как то рукожопно. Код:
|
17.03.2018, 06:39 | #4 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Я думаю, что для поиска двух простых чисел решето неэффективно.
Нужно идти назад прямыми проверками, причем только по числам вида 6n-1, 6n+1 И в лоб проверять делимость на нечётные числа от 5 до sqrt(n) В сумме должно выйти быстрее, особенно для больших n А уж по памяти точно выигрыш будет Последний раз редактировалось Black Fregat; 17.03.2018 в 06:43. |
17.03.2018, 09:06 | #5 |
Пользователь
Регистрация: 12.03.2018
Сообщений: 11
|
|
17.03.2018, 10:20 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Убывающий цикл от 999999999
Вложенный возрастающий цикл до целой части корня переменной первого цикла с проверкой делимости. К 6n-1, 6n+1 можно не привязываться, и так быстро найдет для 10^9 Нашел 2 числа - выход из первого цикла
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
17.03.2018, 12:39 | #7 | |
Пользователь
Регистрация: 12.03.2018
Сообщений: 11
|
Цитата:
Код:
Код:
Последний раз редактировалось rekimchuk; 17.03.2018 в 12:54. |
|
17.03.2018, 12:52 | #8 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
А зачем там массив здоровенный? Два же только найти нужно. И в остальном чушь полная. А с паскаля переведешь на плюсы? Пробуй
Код:
999999929
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
17.03.2018, 13:04 | #9 |
Пользователь
Регистрация: 12.03.2018
Сообщений: 11
|
Спасибо за помощь, теперь надо перевести всё это, а это уже легче(надо лишь человека найти который шарит в паскаль) , я конечно понимаю немножко код. но есть некоторые вещи которые я в паскале не знаю )
|
18.03.2018, 17:48 | #10 |
Пользователь
Регистрация: 12.03.2018
Сообщений: 11
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
С++ Найти сумму всех простых чисел, не превосходящих заданного числа n | Defx | Помощь студентам | 1 | 23.03.2017 12:50 |
Для каждого числа последовательности найти сумму его простых делителей | Aibolat | C++ Builder | 0 | 04.10.2016 10:02 |
Нужно найти сумму всех простых делителей введённого числа | AnnaMV | Общие вопросы C/C++ | 1 | 10.08.2016 08:24 |
програма которая виводит все простие числа от 1 до 1000000 до 1сек | PAWLO1993 | Паскаль, Turbo Pascal, PascalABC.NET | 7 | 12.06.2008 01:15 |