Взаимно простые числа

Обновлено: 08.03.2019

Взаимно простые числа – это целые числа, которые имеют только один общий делитель – единицу.

Метод для проверки, являются ли заданные числа взаимно простыми

public static bool IsCoprime(int num1, int num2)
{
    if (num1 == num2)
    {
        return num1 == 1;
    }
    else
    {
        if (num1 > num2)
        {
            return IsCoprime(num1 - num2, num2);
        }
        else
        {
            return IsCoprime(num2 - num1, num1);
        }
    }
}

Код для проверки взаимной простоты чисел можно сократить используя тернарный оператор:

public static bool IsCoprime(int a, int b)
{
    return a == b 
           ? a == 1 
           : a > b 
                ? IsCoprime(a - b, b) 
                : IsCoprime(b - a, a);
}

Программа для проверки взаимно простых чисел

static void Main(string[] args)
{
    Console.Write("a = ");
    var a = Convert.ToInt32(Console.ReadLine());
    Console.Write("b = ");
    var b = Convert.ToInt32(Console.ReadLine());
    if (IsCoprime(a, b))
    {
        Console.WriteLine("Числа {0} и {1} взаимно простые", a, b);
    }
    else
    {
        Console.WriteLine("Числа {0} и {1} не являются взаимно простыми", a, b);
    }

    Console.ReadLine();
}

Результат работы программы:

65 и 13 взаимно простые числа

Поиск в диапазоне чисел взаимно простых к заданному

static void Main(string[] args)
{
    Console.Write("x = ");
    var x = Convert.ToInt32(Console.ReadLine());
    Console.Write("Начало диапазона: ");
    var s = Convert.ToInt32(Console.ReadLine());
    Console.Write("Конец диапазона: ");
    var e = Convert.ToInt32(Console.ReadLine());

    Console.WriteLine("Взаимно простые числа к числу {0}", x);
    for (int i = s; i < e + 1; i++)
    {
        if (IsCoprime(x, i))
        {
            Console.Write("{0} ", i);
        }
    }

    Console.ReadLine();
}

Результат работы программы:

Взаимно простые числа из диапазона 1..50 к числу 42

Поделиться: Vk Ok