Форум программистов, компьютерный форум CyberForum.ru

Найти пары простых чисел - C++

Войти
Регистрация
Восстановить пароль
 
Kir@
 Аватар для Kir@
86 / 54 / 3
Регистрация: 07.02.2010
Сообщений: 621
03.07.2016, 18:38     Найти пары простых чисел #1
из интервала 1000 до 9999, удовлетворяющих условию (р+1)/q = целое число.

Что-то где-то я пропустил

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <QCoreApplication>
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long j,p,q, result;
 
    for (p=q=j=1000; j<10000; j++)
        if (p%j!=0 && q%j!=0 && (p+1)/q!=0)
        {
            p+=j;
            q+=j;
            result = (p+1)/q;
            cout << p <<" " << q << "Result: " << result << endl;
        }
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2016, 18:38     Найти пары простых чисел
Посмотрите здесь:

Найти суммы каждой пары подряд идущих чисел C++
C++ Среди заданных целых чисел k,l,m найти пары кратных
В массиве целых чисел найти и распечатать все пары одинаковых чисел C++
Найти все пары двузначных чисел, которые, будучи записанными подряд, дают четырёхзначное число, нацело делящееся на сумму данных чисел C++
C++ Нужно найти в массиве и распечатать пары одинаковых чисел
C++ Между n и 2n найти все пары простых чисел, разница которых равна 2
C++ Можно ли разбить последовательность на пары так, чтобы произведение чисел любой пары было одинаковым?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SergioO
 Аватар для SergioO
93 / 182 / 63
Регистрация: 13.12.2015
Сообщений: 986
03.07.2016, 20:35     Найти пары простых чисел #2
пусть
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{p+1}{q}={z}_{+}
z+ положительное, тк и p и q из интервала
далее
http://www.cyberforum.ru/cgi-bin/latex.cgi?p+1=q{z}_{+}
z+ четное, тк p простое и нечетное, следов p+1 - четное и qz+ тоже четное, q простое следов z+ четное, те
http://www.cyberforum.ru/cgi-bin/latex.cgi?p+1=2nq
допустим мы нашли все простые числа из искомого диапазона и 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
и тд
хотя может я и усложняю
HenryDukart
 Аватар для HenryDukart
109 / 109 / 31
Регистрация: 05.10.2013
Сообщений: 429
Завершенные тесты: 2
04.07.2016, 00:06     Найти пары простых чисел #3
Kir@,

Не по теме:

находите элемент простого порядка q?



Добавлено через 13 минут
Kir@,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cmath>
using namespace std;
 
bool is_prime(unsigned long p)
{
    if (p == 2)
        return true;
    if (p % 2 == 0)
        return false;
 
    unsigned long lim = sqrt(p);
    for (int delim = 3; delim < lim; delim += 2)
    {
        if (p % delim == 0)
            return false;
    }
    return true;
}
 
int main()
{
    unsigned long lower_bound = 1000, upper_bound = 10000;
    unsigned long p, q;
    for (p = lower_bound; p < upper_bound; ++p)
    {
        if (is_prime(p))
        {
            for (q = lower_bound; q < upper_bound; ++q)
            {
                if (((p + 1) % q == 0) && is_prime(q))
                {
                    cout << p << " " << q << endl;
                    break;
                }
            }
        }
    }
    return 0;
}
SergioO
 Аватар для SergioO
93 / 182 / 63
Регистрация: 13.12.2015
Сообщений: 986
06.07.2016, 18:31     Найти пары простых чисел #4
HenryDukart, решение в лоб
можете посчитать количество циклов, которые выполняет ваша программа?
Цитата Сообщение от HenryDukart Посмотреть сообщение
for (p = lower_bound; p < upper_bound; ++p)
только здесь на каждый заход будет сколько? 9000?
и сколько так зайти надо? подумаешь 100 тыс циклов на верхнюю границу 10 тыс - это нормально.
если цифры будут, допустим, миллион, да для простых чисел нет такого...
Цитата Сообщение от SergioO Посмотреть сообщение
1. находим все простые числа из диапазона
здесь надо было не все простые числа найти, а максимальное
а далее "резать диапазон", те идити от обратного, а именно смотреть
будет ли (MAX+1)/2 простым и далее "резать" на 4, 6, 8 ... так, на вскудку, 100 шагов, без извлечения корней и тп
притом надо учесть, что делить на 2 можно менять сдвигом битовым, которое поддерживает проц и такая операция делается за такт ))
Цитата Сообщение от SergioO Посмотреть сообщение
2. от MIN до (MAX+1)/2 проверяем содержит ли наше множество 2q - 1
3. от MIN до (MAX+1)/4 -----------------//---------------------- 4q - 1
4. ------------//--- )/6 -----------------//--------------------- 6q - 1
от обратного надо... поторопился.
HenryDukart
 Аватар для HenryDukart
109 / 109 / 31
Регистрация: 05.10.2013
Сообщений: 429
Завершенные тесты: 2
06.07.2016, 18:50     Найти пары простых чисел #5
SergioO, да, мое решение именно "в лоб".

Для проверки числа на простоту на практике используются вероятностные тесты: тест Ферма, тест Рабина-Милера и тест Соловея-Штрассена (второй чаще всего). Не думаю, что автор хотел увидеть именно их.
SergioO
 Аватар для SergioO
93 / 182 / 63
Регистрация: 13.12.2015
Сообщений: 986
06.07.2016, 18:58     Найти пары простых чисел #6
Цитата Сообщение от HenryDukart Посмотреть сообщение
Для проверки числа на простоту на практике используются вероятностные тесты: тест Ферма, тест Рабина-Милера и тест Соловея-Штрассена (второй чаще всего).
это вы в вики прочитали про тесты Соловея-Штрассена?
расскажите может кто и в какой ситуации пользуется этим тестом?
Цитата Сообщение от HenryDukart Посмотреть сообщение
Не думаю, что автор хотел увидеть именно их
автор хотел увидеть готовое решение, что вы и сделали с готовностью.
а где вы увидели что-нибудь подобное?
вычисление простых чисел ведется на суперкомпьютерах непрерывно и вычислены простые числа ... если не ошибаюсь, то последнее простое число занимает на ХДД около 1ГБ, поэтому проверять будут таблицы, если спецслужбы будут ломать и сломают быстро, тк просто будет перебор. вряд ли вы сгенерируете хоть пару МБ простое число.
просто в исходной задаче надо идти сверху и уменьшать диапазон на 2 и там 100 чисел от силы проверить надо.
HenryDukart
 Аватар для HenryDukart
109 / 109 / 31
Регистрация: 05.10.2013
Сообщений: 429
Завершенные тесты: 2
06.07.2016, 19:10     Найти пары простых чисел #7
SergioO,

Не по теме:


Цитата Сообщение от SergioO Посмотреть сообщение
это вы в вики прочитали про тесты Соловея-Штрассена?
расскажите может кто и в какой ситуации пользуется этим тестом?
Нет, не в викии. Я учусь в университете на специальности, связанной с такими вещами. Если вам интересно про эти тесты, можете про них прочитать в интернете, например, в той же википедии.

Возможно, что задача имеет определенный алгоритм. Я об этом не задумывался, не было желаниея.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2016, 23:09     Найти пары простых чисел
Еще ссылки по теме:

Выдать пары простых чисел, разность между которыми равна 4, а сами числа меньше n C++
C++ Найти пары дружественных чисел в диапазоне от 200 до 300
Найти все пары дружественных чисел в диапазоне [n1, n2] C++
В заданном массиве целых чисел найти все пары чисел, удовлетворяющих условию C++
C++ Среди заданных целых чисел k, f, t найти пары кратных

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

Или воспользуйтесь поиском по форуму:
_Ivana
06.07.2016, 23:09     Найти пары простых чисел
  #8

Не по теме:

Цитата Сообщение от HenryDukart Посмотреть сообщение
Я об этом не задумывался, не было желаниея.
Правильно, что тут думать - трясти надо. Тем более, раз
Цитата Сообщение от HenryDukart Посмотреть сообщение
Я учусь в университете на специальности, связанной с такими вещами.

Yandex
Объявления
06.07.2016, 23:09     Найти пары простых чисел
Ответ Создать тему
Опции темы

Текущее время: 16:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru