using System;
namespace ConsoleApp4
{
internal class Program
{
static void Main(string[] args)
{
Console.Write("Введіть n: ");
int n = int.Parse(Console.ReadLine());
PrintAllFracs(n);
}
// 1. Функція для пошуку найбільшого спільного дільника (НСД)
static int CalcGreatestCommonDivisor(int a, int b)
{
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 2. Функція для перевірки, чи є дріб нескоротним
static bool IsFracIrreducible(int a, int b)
{
if (CalcGreatestCommonDivisor(a, b) == 1)
{
return true;
}
else
{
return false;
}
}
// 3. Функція для виведення всіх нескоротних дробів
static void PrintAllFracs(int n)
{
for (int b = 1; b <= n; b++)
{
for (int a = 0; a <= b; a++)
{
if (IsFracIrreducible(a, b))
{
Console.WriteLine(a + "/" + b);
}
}
}
}
}
}
dXNpbmcgU3lzdGVtOwoKbmFtZXNwYWNlIENvbnNvbGVBcHA0CnsKICAgIGludGVybmFsIGNsYXNzIFByb2dyYW0KICAgIHsKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBDb25zb2xlLldyaXRlKCLQktCy0LXQtNGW0YLRjCBuOiAiKTsKICAgICAgICAgICAgaW50IG4gPSBpbnQuUGFyc2UoQ29uc29sZS5SZWFkTGluZSgpKTsKCiAgICAgICAgICAgIFByaW50QWxsRnJhY3Mobik7CiAgICAgICAgfQoKICAgICAgICAvLyAxLiDQpNGD0L3QutGG0ZbRjyDQtNC70Y8g0L/QvtGI0YPQutGDINC90LDQudCx0ZbQu9GM0YjQvtCz0L4g0YHQv9GW0LvRjNC90L7Qs9C+INC00ZbQu9GM0L3QuNC60LAgKNCd0KHQlCkKICAgICAgICBzdGF0aWMgaW50IENhbGNHcmVhdGVzdENvbW1vbkRpdmlzb3IoaW50IGEsIGludCBiKQogICAgICAgIHsKICAgICAgICAgICAgd2hpbGUgKGIgIT0gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IHRlbXAgPSBiOwogICAgICAgICAgICAgICAgYiA9IGEgJSBiOwogICAgICAgICAgICAgICAgYSA9IHRlbXA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIGE7CiAgICAgICAgfQoKICAgICAgICAvLyAyLiDQpNGD0L3QutGG0ZbRjyDQtNC70Y8g0L/QtdGA0LXQstGW0YDQutC4LCDRh9C4INGUINC00YDRltCxINC90LXRgdC60L7RgNC+0YLQvdC40LwKICAgICAgICBzdGF0aWMgYm9vbCBJc0ZyYWNJcnJlZHVjaWJsZShpbnQgYSwgaW50IGIpCiAgICAgICAgewogICAgICAgICAgICBpZiAoQ2FsY0dyZWF0ZXN0Q29tbW9uRGl2aXNvcihhLCBiKSA9PSAxKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gMy4g0KTRg9C90LrRhtGW0Y8g0LTQu9GPINCy0LjQstC10LTQtdC90L3RjyDQstGB0ZbRhSDQvdC10YHQutC+0YDQvtGC0L3QuNGFINC00YDQvtCx0ZbQsgogICAgICAgIHN0YXRpYyB2b2lkIFByaW50QWxsRnJhY3MoaW50IG4pCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGludCBiID0gMTsgYiA8PSBuOyBiKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGEgPSAwOyBhIDw9IGI7IGErKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZiAoSXNGcmFjSXJyZWR1Y2libGUoYSwgYikpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShhICsgIi8iICsgYik7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9