Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
oobarbazanoo
4 / 27 / 8
Регистрация: 13.05.2015
Сообщений: 1,835
1

Алгоритм нахождения простого числа

23.03.2017, 19:42. Просмотров 284. Ответов 10
Метки нет (Все метки)

Подскажите, пожалуйста, алгоритм, который с не более чем логарифмической скоростью находил бы простое число с заданным количеством цифр.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2017, 19:42
Ответы с готовыми решениями:

Алгоритм нахождения минимальных делителей числа
Формат входного файла В первой строке входного файла input.txt находится целое число n (1 ≤ n ≤...

алгоритм нахождения числа квадратов, которые можно получить из прямоугольника
Здравствуйте! Помогите с составлением алгоритма для решения задачи. УсловиеОдна замечательная...

Разработать алгоритм программы, нахождения суммы нечетных цифр целого числа
Разработать алгоритм программы, нахождения суммы нечетных цифр целого числа.

Алгоритм нахождения НОК
Задано два (или более) целых числа (чисел). Составить алгоритм нахождения наименьшего общего...

Алгоритм нахождения кратчейшего маршрута
Есть курьер со своими координатами(Х). Сейчас он имеет три заказа с точкой получения товара(А) и...

10
Shamil1
Модератор
2259 / 1550 / 351
Регистрация: 26.03.2015
Сообщений: 5,533
23.03.2017, 20:49 2
Тест Агравала — Каяла — Саксены?
1
vrm2
325 / 220 / 59
Регистрация: 03.12.2015
Сообщений: 453
Завершенные тесты: 2
23.03.2017, 22:15 3
С заданным количеством цифр? Или не менее, чем заданное количество цифр?
1
oobarbazanoo
4 / 27 / 8
Регистрация: 13.05.2015
Сообщений: 1,835
24.03.2017, 16:30  [ТС] 4
vrm2, с заданным количеством цифр.

Добавлено через 2 минуты
Shamil1, придётся перебирать числа, если взять за основу данный алгоритм... Хотелось бы что-то, что сразу было направленно на отыскание числа. Но думаю такого алгоритма нет. А если учесть то, что растояние между простыми числами длины n сверху ограниченно ln(n). То даёт ли нам это что-то?
0
Shamil1
Модератор
2259 / 1550 / 351
Регистрация: 26.03.2015
Сообщений: 5,533
24.03.2017, 16:49 5
Я не понял, относительно чего Вы меряете скорость... имхо за лог эн Вы даже не сможете посчитать, сколько цифр в числе.
1
oobarbazanoo
4 / 27 / 8
Регистрация: 13.05.2015
Сообщений: 1,835
24.03.2017, 20:33  [ТС] 6
Shamil1, мне не нужно считать ведь количество цифр в числе, если алгоритм будет изначально знать сколько цифр в числе.
0
echs
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
25.03.2017, 10:00 7
oobarbazanoo
Почему бы вам не создать файл прямого доступа,
в который вы запишите к примеру 100 миллионов
простых чисел? Вашей программе останется только
найти (считать) нужные вам числа.
...
PS.
я это делал, считывает число в доли секунды.
1
CoderHuligan
813 / 539 / 201
Регистрация: 30.06.2015
Сообщений: 2,997
Записей в блоге: 13
25.03.2017, 11:31 8
Цитата Сообщение от echs Посмотреть сообщение
я это делал, считывает число в доли секунды.
И сколько "весит" такой файл?
2
echs
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
25.03.2017, 16:07 9
CoderHuligan
Такой файл "весит" ровно 400 000 000 байт
на одно число (любое целое длинное) уходит 4 байта.
1
CoderHuligan
813 / 539 / 201
Регистрация: 30.06.2015
Сообщений: 2,997
Записей в блоге: 13
25.03.2017, 16:51 10
Цитата Сообщение от echs Посмотреть сообщение
Такой файл "весит" ровно 400 000 000 байт
Почти 400 мегабайт...
Не многовато ли?
А если в программу какую-нибудь надо будет вставить?
Кто будет покупать или качать такую пухлую штуковину?
Такой метод имеет смысл только в каких-то специфических приложениях личного или исследовательского характера.
2
echs
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
25.03.2017, 18:00 11
CoderHuligan
Вы понимаете, если вам нужна быстрая программа,
которая намного быстрее любой другой, то память
жалеть не стоит.
Пока "хилая" программа будет считать - эта просто
прочитает свой файл - ведь всё сосчитано!
...
примечание
Это один из способов написания сверх-быстрых программ
- сосчитать то, что и так придется считать...
1
25.03.2017, 18:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2017, 18:00

Алгоритм нахождения вершин многоугольника
Как построить многоугольник с максимальной точностью, если известно: 1.Количество вершин...

Алгоритм нахождения корня слова...
помогите с алгоритмомо выделения корня в слове...отделение корня от других частей слова.......

Алгоритм нахождения пересечений треков
Здравствуйте. Встала задача, в которой понадобился алгоритм нахождения пересечений треков. Вот...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru