Довідник функцій
Яку функцію обрати
| Потрібно | Функція | Приклад |
|---|---|---|
| Перевірити простоту | 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. Перебір усіх можливих дільників простий для розуміння, але для великих чисел потребує багато перевірок.
Довідник функцій
IsPrime: чи є число простим
Просте число більше за 1 і має лише два додатні дільники: 1 та саме себе. Для 2 функція повертає true, для 1 і 9 повертає false.
Прототип: bool IsPrime(int n);
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);
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);
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);
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.
Другий спосіб: повернення структури
Це альтернатива попередній версії. Структура об’єднує два результати.
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
#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 18not prime3 7
Опис функції потрібно розмістити перед її використанням. У цій програмі IsPrime стоїть перед CalcTwoPrimes, а всі власні функції перед main.