Решение задачи Гадание - 2 с Acmp

Без пояснения   Просмотров: 35


Маша недавно прочитала в книге «Теория чисел и предсказание будущего» о новом способе гадания. Способ заключается в следующем: надо выбрать целое положительное число N и посчитать количество чисел, меньших N и взаимно простых с ним. Это количество и будет результатом гадания.

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

Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. Наибольшим общим делителем двух чисел a и b называется наибольшее целое положительное число, на которое делятся и a, и b.

Код

#include <iostream>
#include <cmath>
using namespace std;
bool evklid(int a, int b)
{
    int c = 0;
    while(b){
        c = a;
        a = b;
        b = c % a;
    }
    if(a == 1)
        return 1;
    else
        return 0;
     
}
int main()
{
    int n, a, k = 0;
    cin >> n;
    a = n - 1;
    while(a){
        if(evklid(a, n))
            ++k;
        --a;
    }
    cout << k;
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться