90 / 58 / 7
Регистрация: 07.02.2010
Сообщений: 728
|
||||||
1 | ||||||
Найти пары простых чисел03.07.2016, 18:38. Показов 1492. Ответов 7
Метки нет Все метки)
(
из интервала 1000 до 9999, удовлетворяющих условию (р+1)/q = целое число.
Что-то где-то я пропустил ![]()
0
|
|
03.07.2016, 18:38 | |
Ответы с готовыми решениями:
7
Найти все пары простых чисел, разность между которыми равна 4 Пары взаимно простых чисел
|
260 / 208 / 99
Регистрация: 13.12.2015
Сообщений: 1,098
|
|
03.07.2016, 20:35 | 2 |
пусть
z+ положительное, тк и p и q из интервала далее z+ четное, тк p простое и нечетное, следов p+1 - четное и qz+ тоже четное, q простое следов z+ четное, те допустим мы нашли все простые числа из искомого диапазона и MAX - наибольшее из них, тогда q не может быть больше (MAX+1)/2, т.k. если больше, то q > (MAX+1)/2 <-> 2q-1 > MAX и мы выходим за диапазон 1. находим все простые числа из диапазона 2. от MIN до (MAX+1)/2 проверяем содержит ли наше множество 2q - 1 3. от MIN до (MAX+1)/4 -----------------//---------------------- 4q - 1 4. ------------//--- )/6 -----------------//--------------------- 6q - 1 пока (MAX+1)/2n > q может здесь еще какие тонкости есть структуру, в которую будете простые числа писать надо правильно выбрать: доступ к количеству элементов, минимум, максимум, содержит ли данная структура, например, 2q-1 и тд хотя может я и усложняю
0
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
||||||
04.07.2016, 00:06 | 3 | |||||
Kir@,
Не по теме: находите элемент простого порядка q? Добавлено через 13 минут Kir@,
1
|
260 / 208 / 99
Регистрация: 13.12.2015
Сообщений: 1,098
|
|
06.07.2016, 18:31 | 4 |
HenryDukart, решение в лоб
можете посчитать количество циклов, которые выполняет ваша программа? только здесь на каждый заход будет сколько? 9000? и сколько так зайти надо? подумаешь 100 тыс циклов на верхнюю границу 10 тыс - это нормально. если цифры будут, допустим, миллион, да для простых чисел нет такого... здесь надо было не все простые числа найти, а максимальное а далее "резать диапазон", те идити от обратного, а именно смотреть будет ли (MAX+1)/2 простым и далее "резать" на 4, 6, 8 ... так, на вскудку, 100 шагов, без извлечения корней и тп притом надо учесть, что делить на 2 можно менять сдвигом битовым, которое поддерживает проц и такая операция делается за такт )) от обратного надо... поторопился.
0
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
06.07.2016, 18:50 | 5 |
SergioO, да, мое решение именно "в лоб".
Для проверки числа на простоту на практике используются вероятностные тесты: тест Ферма, тест Рабина-Милера и тест Соловея-Штрассена (второй чаще всего). Не думаю, что автор хотел увидеть именно их.
0
|
260 / 208 / 99
Регистрация: 13.12.2015
Сообщений: 1,098
|
|
06.07.2016, 18:58 | 6 |
это вы в вики прочитали про тесты Соловея-Штрассена?
расскажите может кто и в какой ситуации пользуется этим тестом? автор хотел увидеть готовое решение, что вы и сделали с готовностью. а где вы увидели что-нибудь подобное? вычисление простых чисел ведется на суперкомпьютерах непрерывно и вычислены простые числа ... если не ошибаюсь, то последнее простое число занимает на ХДД около 1ГБ, поэтому проверять будут таблицы, если спецслужбы будут ломать и сломают быстро, тк просто будет перебор. вряд ли вы сгенерируете хоть пару МБ простое число. просто в исходной задаче надо идти сверху и уменьшать диапазон на 2 и там 100 чисел от силы проверить надо.
0
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
06.07.2016, 19:10 | 7 |
SergioO,
Не по теме:
Возможно, что задача имеет определенный алгоритм. Я об этом не задумывался, не было желаниея.
0
|
_Ivana
|
06.07.2016, 23:09
Найти пары простых чисел
#8
|
0
|
06.07.2016, 23:09 | |
Два простых числа называются «близнецами», если они отличаются друг от друга на 2. Найти все пары близнецов, не превышаю В массиве целых чисел найти и распечатать все пары одинаковых чисел
Найти в последовательности натуральных чисел все пары чисел дающие в произведении полный куб Найти количество почти простых чисел в заданном интервале натуральных чисел. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |