Kiểm tra số bất thường (Unusual Number) trong C++

Số bất thường: Ước nguyên tố lớn nhất > √n. Các số đầu: 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 26, 28, 29, 31...

Giải thuật

1. Tìm ước nguyên tố lớn nhất của n
2. So sánh với √n

Tìm ước NT lớn: chia liên tục cho 2, sau đó lẻ từ 3 đến √n, cuối cùng nếu n>2 thì n là ước NT lớn nhất.

Ví dụ minh họa

#include <iostream>
#include <cmath>
using namespace std;

int largestPrimeFactor(int num) {
    int maxPrime = -1;
    while (num % 2 == 0) { maxPrime = 2; num >>= 1; }
    for (int i = 3; i <= sqrt(num); i += 2)
        while (num % i == 0) { maxPrime = i; num /= i; }
    if (num > 2) maxPrime = num;
    return maxPrime;
}

bool isUnusual(int num) {
    return largestPrimeFactor(num) > sqrt(num);
}

int main() {
    int n = 14;
    cout << n << (isUnusual(n) ? " la so bat thuong" : " KHONG la so bat thuong");
}

Kết quả

14 la so bat thuong