0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
|
|
1 | |
Найти количество чисел в интервале от 1 до N, взаимно простых с N23.11.2015, 18:19. Показов 8219. Ответов 11
Метки нет (Все метки)
0
|
23.11.2015, 18:19 | |
Ответы с готовыми решениями:
11
Найти количество натуральных чисел, взаимно простых с данным Найти количество простых чисел в интервале Найти количество простых чисел в заданном интервале Найти количество почти простых чисел в заданном интервале натуральных чисел. |
0 / 0 / 1
Регистрация: 23.11.2015
Сообщений: 4
|
||||||
23.11.2015, 19:05 | 2 | |||||
Сообщение было отмечено Romanchito как решение
Решение
0
|
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
|
|
26.11.2015, 20:37 [ТС] | 3 |
Ваша программа не правильна , так как , если вводить 6 , например , то ответ выводит 2 , что не правильно , так как у 6рки лишь одно взаимное число в промежутке от 1 до 6 , пятерка.
Добавлено через 1 минуту У меня также выводила , в других вариантах , но чтоб она отбрасывала еще и числа имеющие общий делитель , я не знаю как написать(
0
|
0 / 0 / 1
Регистрация: 23.11.2015
Сообщений: 4
|
||||||
26.11.2015, 22:47 | 4 | |||||
Программа почти правильная, она считает 1 взаимно простым числом с 6, поэтому ответ 2.
Если Вы хотите исключить 1, то как вариант добавить в цикл такую запись:
0
|
0 / 0 / 1
Регистрация: 23.11.2015
Сообщений: 4
|
||||||
26.11.2015, 23:47 | 6 | |||||
Ну или оператору a=-1, я думал над этим, но всё же правильнее на мой взгляд исключить 1.
Добавлено через 12 минут Как то так:
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
27.11.2015, 00:25 | 7 |
Если совсем не думать об эффективности, то предложенный код (с соответствующими поправками) должен работать. Но если хоть чуть-чуть о ней задуматься, то код никуда не годиться. Можно пойти таким путем.
Найти все простые делители N и проверять делимость только на них. Но для этого нужен массив (вектор). Правда, не очень большой. Не больше, чем log2N, при чем это очень грубая оценка. Можно воспользоваться еще кой-какими фактами из элементарной (и не очень) теории чисел. В конце концов тут требуется вычислить функцию Эйлера, уж наверное за 300 лет какие-то наработки появились! https://ru.wikipedia.org/wiki/... 1%80%D0%B0 Кстати, в классической формулировке единица входит.
2
|
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
|
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
|
|
01.12.2015, 20:43 [ТС] | 10 |
А можете объяснить почему тут пишется вопрос и двоеточие перед х ?Для чего они?
y ? gcd(y, x%y) : x;
0
|
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 29
|
|
02.12.2015, 18:03 [ТС] | 12 |
Спасибо , что помогли , прям огромное спасибо)))
0
|
02.12.2015, 18:03 | |
02.12.2015, 18:03 | |
Помогаю со студенческими работами здесь
12
Количество чисел взаимно простых с p*q Количество шестизначных чисел, взаимно простых с числом 70 Количество 6-значных чисел, взаимно простых с числом 70 Нахождение простых, взаимно-простых и парно-простых чисел из указанного диапазона Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |