Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
Romanchito
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
1

Найти количество чисел в интервале от 1 до N, взаимно простых с N

23.11.2015, 18:19. Просмотров 1905. Ответов 11
Метки нет (Все метки)

Дано число N. Найти количество чисел в интервале от 1 до N,взаимно простых с N.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.11.2015, 18:19
Ответы с готовыми решениями:

Найти количество простых чисел в заданном интервале
По числу n найти количество простых чисел p из интервала n < p < 2n. Нужен быстрый способ.

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

Определить количество простых чисел в интервале
Определить количество простых чисел в интервале отN до M где N,M-натуальные числа

Подсчитать количество простых чисел в произвольном интервале
Подсчитать количество простых чисел в произвольном интервале. Границы интервала задаются с...

Найти сумму всех простых чисел в интервале от 0 до 1000000
Есть программка считающая сумму всех простых чисел от 0 до 1 млн. Но результат выдает не правильно....

11
Zefirka
0 / 0 / 1
Регистрация: 23.11.2015
Сообщений: 4
23.11.2015, 19:05 2
Лучший ответ Сообщение было отмечено Romanchito как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <conio.h>
using namespace std;
int gcd(int x, int y)
{
    return y ? gcd(y, x%y) : x;
}
int main()
{
    setlocale(LC_ALL, "");
    int a=0, n;
    cout << "Введите число N = ";
    cin >> n;
    for (int k = 0; k < n; k++)
        if (gcd(k, n) == 1)
            a = a + 1;
    cout << "Взаимно простых чисел с числом " << n << ", " << a;
    _getch();
    return 0;
}
0
Romanchito
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
26.11.2015, 20:37  [ТС] 3
Ваша программа не правильна , так как , если вводить 6 , например , то ответ выводит 2 , что не правильно , так как у 6рки лишь одно взаимное число в промежутке от 1 до 6 , пятерка.

Добавлено через 1 минуту
У меня также выводила , в других вариантах , но чтоб она отбрасывала еще и числа имеющие общий делитель , я не знаю как написать(
0
Zefirka
0 / 0 / 1
Регистрация: 23.11.2015
Сообщений: 4
26.11.2015, 22:47 4
Программа почти правильная, она считает 1 взаимно простым числом с 6, поэтому ответ 2.
Если Вы хотите исключить 1, то как вариант добавить в цикл такую запись:
C++
1
2
3
4
5
6
7
    for (int k = 0; k < n; k++)
    {
        if (k = 1)
            a = 0;
        else (gcd(k, n) == 1)
            a = a + 1;
    }
0
26.11.2015, 22:47
Kerry_Jr
Эксперт PHP
2222 / 2016 / 942
Регистрация: 14.05.2014
Сообщений: 5,896
Записей в блоге: 1
Завершенные тесты: 5
26.11.2015, 22:54 5
Цитата Сообщение от Zefirka Посмотреть сообщение
добавить в цикл такую запись:
или не париться и начинать цикл с 2.

Добавлено через 38 секунд
Цитата Сообщение от Zefirka Посмотреть сообщение
C++
1
if (k = 1)
это к бесконечному циклу приведет.
1
Zefirka
0 / 0 / 1
Регистрация: 23.11.2015
Сообщений: 4
26.11.2015, 23:47 6
Ну или оператору a=-1, я думал над этим, но всё же правильнее на мой взгляд исключить 1.

Добавлено через 12 минут
Как то так:
C++
1
2
3
4
5
6
7
    for (int k = 0; k < n; k++)
    {
        if (gcd(k, n) == 1 & k!=1)
            a = a + 1;
        else
            continue;
    }
0
Байт
Эксперт C
21840 / 13631 / 2875
Регистрация: 24.12.2010
Сообщений: 28,990
27.11.2015, 00:25 7
Если совсем не думать об эффективности, то предложенный код (с соответствующими поправками) должен работать. Но если хоть чуть-чуть о ней задуматься, то код никуда не годиться. Можно пойти таким путем.
Найти все простые делители N и проверять делимость только на них. Но для этого нужен массив (вектор). Правда, не очень большой. Не больше, чем log2N, при чем это очень грубая оценка.
Можно воспользоваться еще кой-какими фактами из элементарной (и не очень) теории чисел. В конце концов тут требуется вычислить функцию Эйлера, уж наверное за 300 лет какие-то наработки появились!
https://ru.wikipedia.org/wiki/%D0%A4...B5%D1%80%D0%B0
Кстати, в классической формулировке единица входит.
2
Romanchito
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
29.11.2015, 21:41  [ТС] 8
Большое спасибо , программа работает , только можете поподробнее объяснить про функцию gcd , что она делает , как ее можно представить в алгебраическом виде , и что делает данное выражение в программе
int gcd(int x, int y)
{
return y ? gcd(y, x%y) : x;
}
0
Байт
Эксперт C
21840 / 13631 / 2875
Регистрация: 24.12.2010
Сообщений: 28,990
29.11.2015, 23:35 9
Цитата Сообщение от Romanchito Посмотреть сообщение
про функцию gcd , что она делает
Находит наибольший общий делитель чисел x, y
0
Romanchito
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
01.12.2015, 20:43  [ТС] 10
А можете объяснить почему тут пишется вопрос и двоеточие перед х ?Для чего они?
y ? gcd(y, x%y) : x;
0
Байт
Эксперт C
21840 / 13631 / 2875
Регистрация: 24.12.2010
Сообщений: 28,990
01.12.2015, 21:12 11
Цитата Сообщение от Romanchito Посмотреть сообщение
Для чего они?
Тернарный оператор. Прочитай.
Эквивалентно
C++
1
2
if (y) return gcd(y, x%y);
else return x;
Кто понял и привык, тем легче так.
1
Romanchito
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
02.12.2015, 18:03  [ТС] 12
Спасибо , что помогли , прям огромное спасибо)))
0
02.12.2015, 18:03
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2015, 18:03

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

Упорядочить массив по убыванию количества взаимно простых чисел
Создать случайный массив размера n. Упорядочить его по убыванию количества взаимно простых чисел...

Определить, сколько в последовательности пар соседних взаимно простых чисел
Вводится последовательность из N целых положительных элементов. Определить, сколько в...


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

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

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