C++ / Довідник функцій

Довідник власних функцій

Функції для роботи
з дільниками числа

Призначення, простий код і приклади виклику чотирьох функцій.

Перевірити на своєму числі ↓

Довідник функцій

Яку функцію обрати

ПотрібноФункціяПриклад
Перевірити простотуIsPrime(n)IsPrime(7) → true
Порахувати дільникиNumDiv(n)NumDiv(6) → 4
Знайти суму дільниківSumDiv(n)SumDiv(6) → 12
Подати парне число як суму двох простихCalcTwoPrimes(n, a, b)10 → 3 + 7

У NumDiv і SumDiv враховуємо всі додатні дільники: і 1, і саме число. Для 6 це 1, 2, 3, 6.

У прикладах використовуй невеликі натуральні числа, до 10000. Перебір усіх можливих дільників простий для розуміння, але для великих чисел потребує багато перевірок.

Домовленість довідника: NumDiv і SumDiv для n ≤ 0 повертають −1. IsPrime для n < 2 повертає false. Логічна функція не повертає −1 як ознаку помилки.

Довідник функцій

IsPrime: чи є число простим

Просте число більше за 1 і має лише два додатні дільники: 1 та саме себе. Для 2 функція повертає true, для 1 і 9 повертає false.

Прототип: bool IsPrime(int n);

C++
bool IsPrime(int n) {
    if (n < 2) {
        return false;
    }
    bool prime = true;
    for (int i = 2; i*i <= n; i = i + 1) {
        if (n % i == 0) {
            prime = false;
        }
    }
    return prime;
}

Для n ≥ 2 шукаємо дільники від 2 до n / 2. Якщо знайдено хоча б один, відповідь false. Для 2 і 3 цикл не виконується.

Довідник функцій

NumDiv: кількість дільників

Прототип: int NumDiv(int n);

C++
int NumDiv(int n) {
    if (n <= 0) {
        return -1;
    }
    int count = 0;
    for (int i = 1; i <= n; i = i + 1) {
        if (n % i == 0) {
            count = count + 1;
        }
    }
    return count;
}

NumDiv(1) → 1, NumDiv(6) → 4, NumDiv(12) → 6. Після виявлення дільника збільшуємо лічильник на 1.

Довідник функцій

SumDiv: сума дільників

Прототип: int SumDiv(int n);

C++
int SumDiv(int n) {
    if (n <= 0) {
        return -1;
    }
    int sum = 0;
    for (int i = 1; i <= n; i = i + 1) {
        if (n % i == 0) {
            sum = sum + i;
        }
    }
    return sum;
}

SumDiv(1) → 1, SumDiv(6) → 12, SumDiv(12) → 28. Тут додаємо сам дільник i, а не одиницю.

Сума дільників без самого числа: SumDiv(n) - n. Наприклад, для 6 це 12 − 6 = 6. Саме таку суму використовуємо під час перевірки досконалих чисел.

Довідник функцій

CalcTwoPrimes: сума двох простих чисел

Функція отримує парне n ≥ 4 і шукає a та b, для яких a + b = n і обидва числа прості. Результати записує через параметри за посиланням.

Прототип: void CalcTwoPrimes(int n, int& a, int& b);

C++
void CalcTwoPrimes(int n, int& a, int& b) {
    a = -1;
    b = -1;
    if (n < 4 || n % 2 != 0) {
        return;
    }
    int x = 2;
    while (x <= n / 2 && a == -1) {
        if (IsPrime(x) && IsPrime(n - x)) {
            a = x;
            b = n - x;
        }
        x = x + 1;
    }
}

Перед цією функцією розмісти опис IsPrime. Перевіряємо перше число від 2 до n / 2. Друге дорівнює n − x. Зупиняємося, щойно знайшли першу пару.

Для 4 відповідь 2 і 2, для 10 відповідь 3 і 7. Повторення простого числа дозволене. Для непарного n, n < 4 або якщо пошук не знайшов пари, обидва результати дорівнюють −1.

Команда return; у void-функції завершує її роботу без повернення значення. Тут вона не дозволяє запускати пошук для непридатного n.

Другий спосіб: повернення структури

Це альтернатива попередній версії. Структура об’єднує два результати.

C++
struct TwoIntNums {
    int A;
    int B;
};

TwoIntNums CalcTwoPrimes(int n) {
    TwoIntNums result;
    result.A = -1;
    result.B = -1;
    if (n < 4 || n % 2 != 0) {
        return result;
    }
    int x = 2;
    while (x <= n / 2 && result.A == -1) {
        if (IsPrime(x) && IsPrime(n - x)) {
            result.A = x;
            result.B = n - x;
        }
        x = x + 1;
    }
    return result;
}

Виклик: TwoIntNums answer = CalcTwoPrimes(10);. Результати містяться в answer.A і answer.B.

Так ми перевіряємо подання конкретного числа. Це не є доведенням гіпотези Гольдбаха для всіх парних чисел.

Довідник функцій

Перевір функції на своєму числі

Навчальний приклад: від −10000 до 10000.

Довідник функцій

Повна програма для запуску

Усі чотири функції та приклад main
C++
#include <iostream>
using namespace std;

bool IsPrime(int n) {
    if (n < 2) {
        return false;
    }
    bool prime = true;
    for (int i = 2; i*i <= n; i = i + 1) {
        if (n % i == 0) {
            prime = false;
        }
    }
    return prime;
}

int NumDiv(int n) {
    if (n <= 0) {
        return -1;
    }
    int count = 0;
    for (int i = 1; i <= n; i = i + 1) {
        if (n % i == 0) {
            count = count + 1;
        }
    }
    return count;
}

int SumDiv(int n) {
    if (n <= 0) {
        return -1;
    }
    int sum = 0;
    for (int i = 1; i <= n; i = i + 1) {
        if (n % i == 0) {
            sum = sum + i;
        }
    }
    return sum;
}

void CalcTwoPrimes(int n, int& a, int& b) {
    a = -1;
    b = -1;
    if (n < 4 || n % 2 != 0) {
        return;
    }
    int x = 2;
    while (x <= n / 2 && a == -1) {
        if (IsPrime(x) && IsPrime(n - x)) {
            a = x;
            b = n - x;
        }
        x = x + 1;
    }
}

int main() {
    int n, a, b;
    cin >> n;
    cout << NumDiv(n) << ' ' << SumDiv(n) << '\n';
    if (IsPrime(n)) {
        cout << "prime\n";
    } else {
        cout << "not prime\n";
    }
    CalcTwoPrimes(n, a, b);
    if (a == -1) {
        cout << "no pair";
    } else {
        cout << a << ' ' << b;
    }
    return 0;
}

Для n = 10 вивід:
4 18
not prime
3 7

Опис функції потрібно розмістити перед її використанням. У цій програмі IsPrime стоїть перед CalcTwoPrimes, а всі власні функції перед main.