Question

напишите пожалуйста программу С++

Задача : делители (по возможности используйте только циклы и функции)

Для заданного натурального числа N:

1) найдите все простые числа в диапазоне 1...N

например, N=10 ---> 1, 2, 3, 5, 7

2) найдите все простые несократимые дроби от 0 до 1, знаменатели которых меньше N

например, N=5 ---> 1/1, 1/2, 1/3, 1/4, 2/3, 3/4

3)найти все пары дружественных чисел в диапазоне 1....N (два числа являются дружественными, если каждое из них равно сумме коэффициентов другого, ограниченной самим числом).

например, N=300 ---> 6,6 ; 28,28; 220,284;

Answer 1

Ответ:

Общая структура программы:

1. Функция для нахождения простых чисел:

void printPrimes(int n) {

 bool isPrime[n+1];

 memset(isPrime, true, sizeof(isPrime));

 for (int p=2; p*p<=n; p++) {

   if (isPrime[p]) {

     for (int i=p*p; i<=n; i+=p) {

       isPrime[i] = false;

     }

   }

 }

 for (int p=2; p<=n; p++) {

   if (isPrime[p]) {

     cout << p << " ";

   }

 }

}

2. Функция для нахождения всех простых несократимых дробей:

int gcd(int a, int b) {

 if (a == 0) {

   return b;

 }

 return gcd(b%a, a);

}

void printFractions(int n) {

 for (int i=2; i<=n; i++) {

   for (int j=1; j<i; j++) {

     if (gcd(i, j) == 1) {

       cout << j << "/" << i << " ";

     }

   }

 }

}