Skip to content

🔢 Основни задачи, свързани с делимост на числата

🧮 Делимост на числа

Делимостта е основна концепция в математиката и програмирането. Тя определя дали едно число се дели на друго без остатък. В програмирането се използва операторът % (остатък от деление), за да се провери делимост.

Основни проверки за делимост:

  1. Делимост на 2
    Едно число е четно, ако се дели на 2 без остатък.

    #include <iostream>
using namespace std;

int main() {
    int num;
    cout << "Въведете число: ";
    cin >> num;

    if (num % 2 == 0) {
        cout << num << " е четно число." << endl;
    } else {
        cout << num << " е нечетно число." << endl;
    }
    return 0;
}

  2. Делимост на 3 Едно число е делимо на 3, ако сумата на неговите цифри се дели на 3. 

    #include <iostream>
using namespace std;

bool isDivisibleBy3(int num) {
    int sum = 0;
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum % 3 == 0;
}

int main() {
    int num;
    cout << "Въведете число: ";
    cin >> num;

    if (isDivisibleBy3(num)) {
        cout << num << " е делимо на 3." << endl;
    } else {
        cout << num << " не е делимо на 3." << endl;
    }
    return 0;
}

  3. Делимост на 5 Едно число е делимо на 5, ако завършва на 0 или 5. 

      #include <iostream>
  using namespace std;

  int main() {
      int num;
      cout << "Въведете число: ";
      cin >> num;

      if (num % 5 == 0) {
          cout << num << " е делимо на 5." << endl;
      } else {
          cout << num << " не е делимо на 5." << endl;
      }
      return 0;
  }

📚 Примери за задачи

Намиране на всички числа в интервал, които са делими на дадено число 

#include <iostream>
using namespace std;

int main() {
    int start, end, divisor;
    cout << "Въведете начало на интервала: ";
    cin >> start;
    cout << "Въведете край на интервала: ";
    cin >> end;
    cout << "Въведете делител: ";
    cin >> divisor;

    cout << "Числа, делими на " << divisor << ": ";
    for (int i = start; i <= end; i++) {
        if (i % divisor == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

Сумиране на числа, които са делими на дадено число 

#include <iostream>
using namespace std;

int main() {
    int start, end, divisor, sum = 0;
    cout << "Въведете начало на интервала: ";
    cin >> start;
    cout << "Въведете край на интервала: ";
    cin >> end;
    cout << "Въведете делител: ";
    cin >> divisor;

    for (int i = start; i <= end; i++) {
        if (i % divisor == 0) {
            sum += i;
        }
    }

    cout << "Сумата на числата, делими на " << divisor << ", е: " << sum << endl;
    return 0;
}

Проверка дали дадено число е просто 

#include <iostream>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= num / 2; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int num;
    cout << "Въведете число: ";
    cin >> num;

    if (isPrime(num)) {
        cout << num << " е просто число." << endl;
    } else {
        cout << num << " не е просто число." << endl;
    }
    return 0;
}

🔍 Напреднали проверки за делимост

Делимост на 4

Едно число е делимо на 4, ако последните му две цифри образуват число, което се дели на 4: 

bool isDivisibleBy4(int num) {
    int lastTwo = num % 100;
    return lastTwo % 4 == 0;
}

Делимост на 6

Числото трябва да се дели едновременно на 2 и на 3: 

bool isDivisibleBy6(int num) {
    return (num % 2 == 0) && (isDivisibleBy3(num));
}

Делимост на 7 (Усложнена проверка)

Метод: Отделяме последната цифра, умножаваме я по 2 и я изваждаме от останалото число. Повтаряме процеса: 

bool isDivisibleBy7(int num) {
    if (num < 0) num = -num;
    if (num == 0 || num == 7) return true;
    if (num < 10) return false;

    return isDivisibleBy7(num / 10 - 2 * (num % 10));
}

Делимост на 8

Последните три цифри образуват число, делимо на 8: 

bool isDivisibleBy8(int num) {
    int lastThree = num % 1000;
    return lastThree % 8 == 0;
}

Делимост на 9

Сумата на цифрите се дели на 9: 

bool isDivisibleBy9(int num) {
    int sum = 0;
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum % 9 == 0;
}

Делимост на 11

Разликата между сумата на цифрите на нечетни позиции и сумата на цифрите на четни позиции се дели на 11: 

bool isDivisibleBy11(int num) {
    int oddSum = 0, evenSum = 0;
    bool isOdd = true;

    while (num != 0) {
        if (isOdd) {
            oddSum += num % 10;
        } else {
            evenSum += num % 10;
        }
        num /= 10;
        isOdd = !isOdd;
    }

    int diff = oddSum - evenSum;
    return (diff % 11 == 0);
}

🧮 Най-голям общ делител (НОД)

НОД на две числа е най-голямото число, което дели и двете без остатък.

Алгоритъм на Евклид

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Рекурсивна версия
int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);
}

// C++17 стандартна функция
#include <numeric>
int result = std::gcd(a, b);

НОД на повече от две числа

int gcdMultiple(vector<int>& arr) {
    int result = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        result = gcd(result, arr[i]);
        if (result == 1) break; // Оптимизация
    }
    return result;
}

🔢 Най-малко общо кратно (НОК)

НОК на две числа е най-малкото число, което се дели и на двете.

Формула: \(\text{НОК}(a, b) = \frac{a \times b}{\text{НОД}(a, b)}\)

long long lcm(int a, int b) {
    return (long long)a * b / gcd(a, b);
}

// За избягване на overflow
long long lcmSafe(int a, int b) {
    return (long long)a / gcd(a, b) * b;
}

// C++17
#include <numeric>
long long result = std::lcm(a, b);

🌟 Прости числа

Проверка за простота (Оптимизирана)

bool isPrimeOptimized(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;

    // Проверяваме само числа от вида 6k ± 1
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    return true;
}

Намиране на всички прости делители

vector<int> primeFactors(int num) {
    vector<int> factors;

    while (num % 2 == 0) {
        factors.push_back(2);
        num /= 2;
    }

    for (int i = 3; i * i <= num; i += 2) {
        while (num % i == 0) {
            factors.push_back(i);
            num /= i;
        }
    }

    if (num > 2) {
        factors.push_back(num);
    }

    return factors;
}

Сито на Ератостен

Намиране на всички прости числа до N: 

vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

📊 Съвършени, недостатъчни и изобилни числа

Съвършено число

Сумата на собствените делители е равна на самото число: 

bool isPerfect(int num) {
    int sum = 1; // 1 винаги е делител

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            sum += i;
            if (i != num / i) {
                sum += num / i;
            }
        }
    }

    return sum == num && num != 1;
}
// Примери: 6, 28, 496, 8128

Изобилно число

Сумата на собствените делители е по-голяма от числото: 

bool isAbundant(int num) {
    int sum = 1;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            sum += i;
            if (i != num / i) sum += num / i;
        }
    }
    return sum > num;
}
// Примери: 12, 18, 20, 24

🔄 Обръщане и палиндромни числа

Обръщане на число

int reverseNumber(int num) {
    int reversed = 0;

    while (num != 0) {
        reversed = reversed * 10 + num % 10;
        num /= 10;
    }

    return reversed;
}

Проверка за палиндромно число

bool isPalindromeNumber(int num) {
    if (num < 0) return false;
    return num == reverseNumber(num);
}

🎲 Числа на Армстронг (Нарцистични числа)

Числото е равно на сумата на цифрите си, повдигнати на степен, равна на броя цифри: 

bool isArmstrong(int num) {
    int original = num;
    int sum = 0;
    int digits = to_string(num).length();

    while (num != 0) {
        int digit = num % 10;
        sum += pow(digit, digits);
        num /= 10;
    }

    return sum == original;
}
// Примери: 153 = 1³ + 5³ + 3³
//          9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

🔢 Сума и произведение на цифрите

Сума на цифрите

int digitSum(int num) {
    int sum = 0;
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

Произведение на цифрите

int digitProduct(int num) {
    int product = 1;
    while (num != 0) {
        product *= num % 10;
        num /= 10;
    }
    return product;
}

🎯 Олимпиадни задачи

Задача 1: Намиране на брой делители

int countDivisors(int num) {
    int count = 0;
    for (int i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            count++;
            if (i != num / i) {
                count++;
            }
        }
    }
    return count;
}

Задача 2: Сума на делителите

int sumOfDivisors(int num) {
    int sum = 0;
    for (int i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            sum += i;
            if (i != num / i && i != 1) {
                sum += num / i;
            }
        }
    }
    return sum;
}

Задача 3: Числа на Фибоначи, които са прости

void primeFibonacci(int n) {
    long long a = 0, b = 1;

    for (int i = 0; i < n; i++) {
        if (isPrimeOptimized(b)) {
            cout << b << " ";
        }
        long long next = a + b;
        a = b;
        b = next;
    }
}

Задача 4: Приятелски числа

Две числа са приятелски, ако сумата на делителите на едното е равна на другото: 

bool areAmicable(int a, int b) {
    return sumOfDivisors(a) == b && sumOfDivisors(b) == a;
}
// Пример: 220 и 284

💡 Важни съвети

  1. Оптимизация на делимост: Проверявайте само до √n при търсене на делители
  2. Използвайте long long: При умножение на големи числа за избягване на overflow
  3. Кеширайте резултати: Ако проверявате делимост многократно, използвайте Сито
  4. Внимавайте с отрицателни числа: Модулната операция може да даде неочаквани резултати

🏁 Заключение

Задачите за делимост са фундаментални в програмирането и често се срещат в олимпиади. От прости проверки за четност до сложни алгоритми като сито на Ератостен, овладяването на тези техники е критично за успеха. Практикувайте редовно, запомнете признаците за делимост и експериментирайте с различни оптимизации! 🚀