90 / 58 / 7
Регистрация: 07.02.2010
Сообщений: 728
1

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

03.07.2016, 18:38. Показов 1492. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
из интервала 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.07.2016, 18:38
Ответы с готовыми решениями:

Между n и 2n найти все пары простых чисел, разница которых равна 2
Нужна написать программу на с++ для решение задачи. Между n и 2n найти все пары простых чисел,...

Найти все пары простых чисел, разность между которыми равна 4
Дано натуральное число n&gt;13. Найти все пары простых чисел, разность между которыми равна 4 Каждое...

Пары взаимно простых чисел
Дано число n(кол-во чисел) и числа а(интервал этих чисел)(1..n) (n&lt;100). Вывести все пары взаимно...

Выдать пары простых чисел, разность между которыми равна 4, а сами числа меньше n
Дано натуральное число n&gt;13. Выдать пары простых чисел, разность между которыми равна 4, а сами...

7
260 / 208 / 99
Регистрация: 13.12.2015
Сообщений: 1,098
03.07.2016, 20:35 2
пусть
https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{p+1}{q}={z}_{+}
z+ положительное, тк и p и q из интервала
далее
https://www.cyberforum.ru/cgi-bin/latex.cgi?p+1=q{z}_{+}
z+ четное, тк p простое и нечетное, следов p+1 - четное и qz+ тоже четное, q простое следов z+ четное, те
https://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
и тд
хотя может я и усложняю
0
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
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;
}
1
260 / 208 / 99
Регистрация: 13.12.2015
Сообщений: 1,098
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
от обратного надо... поторопился.
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
Цитата Сообщение от HenryDukart Посмотреть сообщение
Для проверки числа на простоту на практике используются вероятностные тесты: тест Ферма, тест Рабина-Милера и тест Соловея-Штрассена (второй чаще всего).
это вы в вики прочитали про тесты Соловея-Штрассена?
расскажите может кто и в какой ситуации пользуется этим тестом?
Цитата Сообщение от HenryDukart Посмотреть сообщение
Не думаю, что автор хотел увидеть именно их
автор хотел увидеть готовое решение, что вы и сделали с готовностью.
а где вы увидели что-нибудь подобное?
вычисление простых чисел ведется на суперкомпьютерах непрерывно и вычислены простые числа ... если не ошибаюсь, то последнее простое число занимает на ХДД около 1ГБ, поэтому проверять будут таблицы, если спецслужбы будут ломать и сломают быстро, тк просто будет перебор. вряд ли вы сгенерируете хоть пару МБ простое число.
просто в исходной задаче надо идти сверху и уменьшать диапазон на 2 и там 100 чисел от силы проверить надо.
0
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
06.07.2016, 19:10 7
SergioO,

Не по теме:


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

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

0
_Ivana
06.07.2016, 23:09     Найти пары простых чисел
  #8

Не по теме:

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.07.2016, 23:09

Пользователь вводит пары целых чисел. Вычислить площади прямоугольников, сторонами которых являются эти пары чисел
Пользователь вводит пары целых чисел. Вычислить площади прямоугольников, сторонами которых являются...

Два простых числа называются «близнецами», если они отличаются друг от друга на 2. Найти все пары близнецов, не превышаю
помогите решить Два простых числа называются «близнецами», если они отличаются друг от друга на 2....

В массиве целых чисел найти и распечатать все пары одинаковых чисел
В массиве целых чисел найти и распечатать все пары одинаковых чисел. За помощь буду очень...

В заданном массиве целых чисел найти все пары чисел, удовлетворяющих условию
Дан массив целых чисел а0, ..., аn-1. Найти все пары (аi, аi+1), такие, что аi = 0 и аi+1 кратно 2.

Найти в последовательности натуральных чисел все пары чисел дающие в произведении полный куб
Напишите эффективную по времени программу, находящую в последовательности натуральных чисел не...

Найти количество почти простых чисел в заданном интервале натуральных чисел.
Натуральное число называется почти простым, если оно не простое и имеет только один простой...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru