Взаємно прості числа

Оновлено: 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