Lập trình C/C++

Thuật toán về các số nguyên đặc biệt (Full Code)

Posted on by Đỗ Thành
Thầy giáo dạy lập trình
03
Th2
View: 49

Số nguyên tố

Kiểm tra số nguyên tố (Trial Division)

Khi kiểm tra một số nguyên tố, thay vì kiểm tra mọi số từ 2 đến sqrt(n), ta chỉ cần kiểm tra các số dạng 6k ± 1 nhỏ hơn hoặc bằng sqrt(n). Điều này giúp giảm đáng kể số lượng phép chia cần thực hiện.

Code tham khảo:

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true; // 2 và 3 là số nguyên tố
    if (n % 2 == 0 || n % 3 == 0) return false;

    // Kiểm tra các số dạng 6k ± 1
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

int main() {
    int n;
    cout << "Nhập số cần kiểm tra: ";
    cin >> n;
    if (isPrime(n))
        cout << n << " là số nguyên tố." << endl;
    else
        cout << n << " không là số nguyên tố." << endl;
    return 0;
}

Sàng Eratosthenes (Sieve of Eratosthenes)

Sàng Eratosthenes là một thuật toán cổ điển và hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương nn cho trước. Thuật toán này được đặt theo tên của nhà toán học Hy Lạp cổ đại Eratosthenes, người đã phát minh ra nó.

Nguyên lý hoạt động:

  • Bước 1: Tạo một danh sách các số nguyên từ 2 đến n. Ban đầu, tất cả các số đều được coi là số nguyên tố.
  • Bước 2: Bắt đầu từ số đầu tiên (2), đánh dấu tất cả các bội số của nó (4, 6, 8, …) là không phải số nguyên tố.
  • Bước 3: Chuyển sang số tiếp theo chưa bị đánh dấu (3), và đánh dấu tất cả các bội số của nó (6, 9, 12, …) là không phải số nguyên tố.
  • Bước 4: Lặp lại quá trình này cho đến khi đã xét tất cả các số từ 2 đến n​. Các số không bị đánh dấu sau cùng là các số nguyên tố.

Code tham khảo:

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

vector<bool> sieveOfEratosthenes(int n) {
    // Tạo một mảng boolean để đánh dấu các số nguyên tố
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; 

    // Bắt đầu từ số đầu tiên là 2
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            // Đánh dấu các bội số của i là không phải số nguyên tố
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    int n;
    cout << "Nhập giới hạn n: ";
    cin >> n;

    vector<bool> sieve = sieveOfEratosthenes(n);
    cout << "Các số nguyên tố từ 2 đến " << n << " là: ";
    for (int i = 2; i <= n; ++i) {
        if (sieve[i]) cout << i << " ";
    }
    cout << endl;
    return 0;
}

Sàng phân đoạn (Segmented Sieve)

Sàng phân đoạn (Segmented Sieve) là một phương pháp tối ưu để tìm tất cả các số nguyên tố trong một khoảng cụ thể [L, R], đặc biệt khi khoảng này lớn và không thể sử dụng Sàng Eratosthenes thông thường do giới hạn bộ nhớ.

Nguyên lý hoạt động:

  • Bước 1: Sử dụng Sàng Eratosthenes để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng √R. Các số nguyên tố này sẽ được dùng để đánh dấu các bội số trong khoảng [L, R].
  • Bước 2: Khởi tạo một mảng boolean có kích thước (R – L + 1) để đánh dấu các số trong khoảng [L, R]. Ban đầu, tất cả các phần tử được coi là số nguyên tố (true).
  • Bước 3: Với mỗi số nguyên tố p tìm được ở Bước 1, đánh dấu các bội số của p trong khoảng [L, R] là không phải số nguyên tố (false).
  • Bước 4: Thu thập các số không bị đánh dấu (tức là số nguyên tố) trong khoảng [L, R].

Code tham khảo:

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

// Sàng Eratosthenes tìm các số nguyên tố nhỏ hơn hoặc bằng 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;
}

// Sàng phân đoạn để tìm các số nguyên tố trong khoảng [L, R]
vector<int> segmentedSieve(int L, int R) {
    // Bước 1: Tìm các số nguyên tố nhỏ hơn hoặc bằng sqrt(R)
    int limit = sqrt(R);
    vector<bool> baseSieve = sieveOfEratosthenes(limit);

    // Lưu các số nguyên tố nhỏ hơn hoặc bằng sqrt(R)
    vector<int> primes;
    for (int i = 2; i <= limit; ++i) {
        if (baseSieve[i]) primes.push_back(i);
    }

    // Bước 2: Khởi tạo sàng cho đoạn [L, R]
    vector<bool> segSieve(R - L + 1, true);

    // Xử lý trường hợp đặc biệt khi L = 0 hoặc 1
    if (L == 0) segSieve[0] = segSieve[1] = false;
    else if (L == 1) segSieve[0] = false;

    // Bước 3: Đánh dấu các bội số của các số nguyên tố trong đoạn [L, R]
    for (int p : primes) {
        // Tìm số nhỏ nhất trong đoạn [L, R] là bội số của p
        int start = max(p * p, (L + p - 1) / p * p);
        for (int j = start; j <= R; j += p) {
            segSieve[j - L] = false;
        }
    }

    // Bước 4: Thu thập các số nguyên tố trong đoạn [L, R]
    vector<int> result;
    for (int i = 0; i < segSieve.size(); ++i) {
        if (segSieve[i]) result.push_back(L + i);
    }
    return result;
}

int main() {
    int L, R;
    cout << "Nhập khoảng [L, R]: ";
    cin >> L >> R;

    vector<int> primes = segmentedSieve(L, R);
    cout << "Các SNT trong khoảng [" << L << ", " << R << "] là: ";
    for (int p : primes) cout << p << " ";
    cout << endl;

    return 0;
}

Bài tập tham khảo

Bài tập 1. Kiểm tra số siêu nguyên tố

Một số được gọi là số siêu nguyên tố nếu tất cả các tiền tố của nó cũng là số nguyên tố. Ví dụ, 3797 là số siêu nguyên tố vì 3, 37, 379 và 3797 đều là số nguyên tố. Hãy viết chương trình kiểm tra xem một số nguyên dương n nhập từ bàn phím có phải là số siêu nguyên tố không.

Code tham khảo:

#include <iostream>
using namespace std;

// Kiểm tra số nguyên tố với thuật toán 6k ± 1
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;  // 2 và 3 là số nguyên tố
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// Kiểm tra số siêu nguyên tố
bool isSuperPrime(int n) {
    while (n > 0) {
        if (!isPrime(n)) return false;
        n /= 10;  // Loại bỏ chữ số cuối
    }
    return true;
}

int main() {
    int n;
    cout << "Nhap so nguyen duong n: ";
    cin >> n;

    if (isSuperPrime(n)) {
        cout << n << " la so sieu nguyen to.\n";
    } else {
        cout << n << " khong phai so sieu nguyen to.\n";
    }

    return 0;
}

Liệt kê các số siêu nguyên tố từ 1 đến n:

#include <iostream>
using namespace std;

// Kiểm tra số nguyên tố với thuật toán 6k ± 1
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// Kiểm tra số siêu nguyên tố
bool isSuperPrime(int n) {
    while (n > 0) {
        if (!isPrime(n)) return false;
        n /= 10;  // Loại bỏ chữ số cuối
    }
    return true;
}

int main() {
    int n;
    cout << "Nhap so nguyen duong n: ";
    cin >> n;

    cout << "Cac so sieu nguyen to tu 1 den " << n << ":\n";
    bool found = false;

    for (int i = 1; i <= n; i++) {
        if (isSuperPrime(i)) {
            cout << i << " ";
            found = true;
        }
    }

    if (!found) {
        cout << "Khong co so sieu nguyen to trong khoang tu 1 den " << n << ".";
    }

    cout << endl;
    return 0;
}

Bài tập 2. Số nguyên tố Palindrome

Một số Palindrome là số đối xứng, ví dụ: 131, 757. Viết chương trình tìm tất cả các số nguyên tố Palindrome nhỏ hơn n.
Ví dụ: Với n=1000, kết quả là: 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929.

Code tham khảo:

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

// Kiểm tra số nguyên tố với thuật toán 6k ± 1
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// Kiểm tra số Palindrome
bool isPalindrome(int n) {
    int original = n, reversed = 0;

    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }

    return original == reversed;
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    cout << "Cac so nguyen to Palindrome nho hon " << n << " la:\n";
    bool found = false;

    for (int i = 2; i < n; i++) {
        if (isPrime(i) && isPalindrome(i)) {
            cout << i << " ";
            found = true;
        }
    }

    if (!found) {
        cout << "Khong co so nao nho hon " << n << ".";
    }

    cout << endl;
    return 0;
}

Sử dụng sàng nguyên tố:

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

// Sử dụng sàng Eratosthenes để tìm các số nguyên tố nhỏ hơn 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;
}

// Kiểm tra số Palindrome
bool isPalindrome(int n) {
    int original = n, reversed = 0;

    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }

    return original == reversed;
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    // Sử dụng sàng để tìm số nguyên tố
    vector<bool> isPrime = sieveOfEratosthenes(n);

    cout << "Cac so nho hon " << n << " la:\n";
    bool found = false;

    for (int i = 2; i < n; i++) {
        if (isPrime[i] && isPalindrome(i)) {
            cout << i << " ";
            found = true;
        }
    }

    if (!found) {
        cout << "Khong co so nao nho hon " << n << ".";
    }

    cout << endl;
    return 0;
}

Bài tập 3. Phân tích số thành tổng các số nguyên tố

Viết chương trình tìm tất cả các cách phân tích một số nguyên n thành tổng của các số nguyên tố.
Ví dụ: Với n=10, kết quả là:

  • 2 + 2 + 2 + 2 + 2
  • 2 + 3 + 5
  • 5 + 5

Cách 1. Sử dụng sàng nguyên tố kết hợp đệ quy:

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

// Sàng Eratosthenes để tìm tất cả số nguyên tố nhỏ hơn hoặc bằng n
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;

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

    return primes;
}

// In một tổ hợp thỏa mãn
void printCombination(const vector<int>& combination) {
    for (int i = 0; i < combination.size(); i++) {
        if (i > 0) cout << " + ";
        cout << combination[i];
    }
    cout << endl;
}

// Hàm đệ quy tìm các tổ hợp
void findPrimeSumCombinations(int n, int startIdx, vector<int>& combination, const vector<int>& primes) {
    if (n == 0) {
        printCombination(combination);
        return;
    }

    for (int i = startIdx; i < primes.size() && primes[i] <= n; i++) {
        combination.push_back(primes[i]);
        findPrimeSumCombinations(n - primes[i], i, combination, primes);
        combination.pop_back();
    }
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    if (n < 2) {
        cout << "Khong co cach phan tich do n qua nho.\n";
        return 0;
    }

    // Tìm danh sách các số nguyên tố nhỏ hơn hoặc bằng n
    vector<int> primes = sieveOfEratosthenes(n);
    vector<int> combination;

    cout << "Cac cach phan tich " << n << " thanh tong cac so nguyen to:\n";
    findPrimeSumCombinations(n, 0, combination, primes);

    return 0;
}

Cách 2. Sử dụng sàng nguyên tố kết hợp quy hoạch động:

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

// Sàng Eratosthenes tìm tất cả số nguyên tố <= n
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;

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

    return primes;
}

int countPrimeSumWays(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // Cách duy nhất để đạt được tổng 0

    vector<int> primes = sieveOfEratosthenes(n);

    for (int prime : primes) {
        for (int i = prime; i <= n; i++) {
            dp[i] += dp[i - prime];
        }
    }

    return dp[n];
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;

    if (n < 2) {
        cout << "Khong co cach phan tich do n qua nho." << endl;
        return 0;
    }

    int result = countPrimeSumWays(n);
    cout << "So cach phan tich " << n << " thanh tong cac so nguyen to la: " << result << endl;

    return 0;
}

Bài tập 4. Dãy nguyên tố liên tiếp có tổng lớn nhất

Cho số nguyên dương n. Hãy tìm dãy các số nguyên tố liên tiếp có tổng lớn nhất nhỏ hơn hoặc bằng n.
Ví dụ: Với n=100, dãy có tổng lớn nhất là: 2 + 3 + 5 + 7 + 11 + 13 = 41.

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// Hàm kiểm tra số nguyên tố sử dụng công thức 6k ± 1
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;

    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

// Hàm tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng n
vector<int> generatePrimes(int n) {
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (isPrime(i)) {
            primes.push_back(i);
        }
    }
    return primes;
}

// Hàm tìm dãy số nguyên tố liên tiếp có tổng lớn nhất
vector<int> findMaxPrimeSequence(int n) {
    vector<int> primes = generatePrimes(n);

    vector<int> result;
    int maxSum = 0;
    int maxLength = 0;

    for (size_t i = 0; i < primes.size(); ++i) {
        int sum = 0;
        for (size_t j = i; j < primes.size(); ++j) {
            sum += primes[j];
            if (sum > n) break;
            if (isPrime(sum) && (j - i + 1) > maxLength) {
                maxLength = j - i + 1;
                maxSum = sum;
                result.assign(primes.begin() + i, primes.begin() + j + 1);
            }
        }
    }

    return result;
}

int main() {
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    vector<int> sequence = findMaxPrimeSequence(n);

    cout << "Dãy số nguyên tố liên tiếp có tổng lớn nhất nhỏ hơn hoặc bằng " << n << " là: ";
    for (int num : sequence) {
        cout << num << " ";
    }
    cout << endl;

    int sum = 0;
    for (int num : sequence) {
        sum += num;
    }
    cout << "Tổng của dãy số này là: " << sum << endl;

    return 0;
}

Sử dụng sàng nguyên tố:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm sàng nguyên tố (Sieve of Eratosthenes)
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải số nguyên tố

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

    vector<int> primes;
    for (int p = 2; p <= n; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }

    return primes;
}

// Hàm tìm dãy số nguyên tố liên tiếp có tổng lớn nhất
vector<int> findMaxPrimeSequence(int n) {
    vector<int> primes = sieveOfEratosthenes(n);

    vector<int> result;
    int maxSum = 0;
    int maxLength = 0;

    for (size_t i = 0; i < primes.size(); ++i) {
        int sum = 0;
        for (size_t j = i; j < primes.size(); ++j) {
            sum += primes[j];
            if (sum > n) break;
            if (binary_search(primes.begin(), primes.end(), sum) && (j - i + 1) > maxLength) {
                maxLength = j - i + 1;
                maxSum = sum;
                result.assign(primes.begin() + i, primes.begin() + j + 1);
            }
        }
    }

    return result;
}

int main() {
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    vector<int> sequence = findMaxPrimeSequence(n);

    cout << "Dãy số nguyên tố liên tiếp có tổng lớn nhất nhỏ hơn hoặc bằng " << n << " là: ";
    for (int num : sequence) {
        cout << num << " ";
    }
    cout << endl;

    int sum = 0;
    for (int num : sequence) {
        sum += num;
    }
    cout << "Tổng của dãy số này là: " << sum << endl;

    return 0;
}

Bài tập 5. Số nguyên tố có chữ số là số nguyên tố

Viết chương trình kiểm tra xem một số nguyên n có phải là số nguyên tố mà tất cả các chữ số của nó cũng là số nguyên tố hay không.
Ví dụ:

  • n=37 → Kết quả: Đúng (vì 3 và 7 đều là số nguyên tố).
  • n=49 → Kết quả: Sai.

Code tham khảo:

#include <iostream>
#include <cmath>

using namespace std;

// Hàm kiểm tra số nguyên tố
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;

    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

// Hàm kiểm tra các chữ số của số n có là số nguyên tố hay không
bool areDigitsPrime(int n) {
    while (n > 0) {
        int digit = n % 10; // Lấy chữ số cuối cùng
        if (!isPrime(digit)) {
            return false; // Chữ số không nguyên tố, trả về false
        }
        n /= 10; // Loại bỏ chữ số cuối cùng
    }
    return true; // Tất cả các chữ số đều là số nguyên tố
}

// Hàm kiểm tra số nguyên tố có chữ số là số nguyên tố
bool isPrimeWithPrimeDigits(int n) {
    return isPrime(n) && areDigitsPrime(n);
}

int main() {
    int n;
    cout << "Nhập số nguyên n: ";
    cin >> n;

    if (isPrimeWithPrimeDigits(n)) {
        cout << "Kết quả: Đúng" << endl;
    } else {
        cout << "Kết quả: Sai" << endl;
    }

    return 0;
}

Sử dụng sàng nguyên tố:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Hàm sàng nguyên tố (Sieve of Eratosthenes)
vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải số nguyên tố

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

    return isPrime;
}

// Hàm kiểm tra các chữ số của số n có là số nguyên tố hay không
bool areDigitsPrime(int n, const vector<bool>& isPrime) {
    while (n > 0) {
        int digit = n % 10; // Lấy chữ số cuối cùng
        if (!isPrime[digit]) {
            return false; // Chữ số không nguyên tố, trả về false
        }
        n /= 10; // Loại bỏ chữ số cuối cùng
    }
    return true; // Tất cả các chữ số đều là số nguyên tố
}

// Hàm kiểm tra số nguyên tố có chữ số là số nguyên tố
bool isPrimeWithPrimeDigits(int n, const vector<bool>& isPrime) {
    return isPrime[n] && areDigitsPrime(n, isPrime);
}

int main() {
    int n;
    cout << "Nhập số nguyên n: ";
    cin >> n;

    // Tạo sàng nguyên tố với giới hạn là n
    vector<bool> isPrime = sieveOfEratosthenes(n);

    if (isPrimeWithPrimeDigits(n, isPrime)) {
        cout << "Kết quả: Đúng" << endl;
    } else {
        cout << "Kết quả: Sai" << endl;
    }

    return 0;
}

Bài tập 6. Đếm số nguyên tố trong đoạn [L, R]

Cho hai số nguyên L và R. Hãy viết chương trình đếm số lượng số nguyên tố trong đoạn từ L đến R.
Ví dụ: Với L=10, R=50 → Kết quả: 10 (11, 13, 17, 19, 23, 29, 31, 37, 41, 43).

Cách 1. Sử dụng công thức 6k  ± 1:

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

// Hàm kiểm tra số nguyên tố
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Hàm đếm số lượng số nguyên tố trong đoạn [L, R]
int countPrimes(int L, int R) {
    int count = 0;
    for (int i = L; i <= R; ++i) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}

int main() {
    int L, R;
    cout << "Nhập L: ";
    cin >> L;
    cout << "Nhập R: ";
    cin >> R;

    int result = countPrimes(L, R);
    cout << "Số lượng số nguyên tố trong đoạn [" << L << " , " << R << "] là: " << result << endl;

    return 0;
}

Cách 2. Sử dụng sàng nguyên tố:

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

// Hàm Sàng Nguyên Tố
void sieve(vector<bool> &isPrime, int maxNum) {
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải là số nguyên tố
    for (int i = 2; i * i <= maxNum; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// Hàm đếm số lượng số nguyên tố trong đoạn [L, R]
int countPrimes(int L, int R) {
    int maxNum = R;
    vector<bool> isPrime(maxNum + 1, true);
    sieve(isPrime, maxNum);

    int count = 0;
    for (int i = L; i <= R; ++i) {
        if (isPrime[i]) {
            count++;
        }
    }
    return count;
}

int main() {
    int L, R;
    cout << "Nhập L: ";
    cin >> L;
    cout << "Nhập R: ";
    cin >> R;

    int result = countPrimes(L, R);
    cout << "Số lượng số nguyên tố trong đoạn [" << L << " , " << R << "] là: " << result << endl;

    return 0;
}

Bài tập 7. Tìm cặp số nguyên tố sinh đôi (Twin Primes)

Hai số nguyên tố được gọi là cặp số nguyên tố sinh đôi nếu hiệu của chúng bằng 2, ví dụ: 3 và 5, 11 và 13. Viết chương trình tìm tất cả các cặp số nguyên tố sinh đôi nhỏ hơn hoặc bằng n.
Ví dụ: Với n=20, kết quả là: (3, 5), (5, 7), (11, 13), (17, 19).

Cách 1. Sử dụng công thức 6k  ± 1:

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

// Hàm kiểm tra số nguyên tố
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Hàm tìm các cặp số nguyên tố sinh đôi nhỏ hơn hoặc bằng n
vector<pair<int, int>> findTwinPrimes(int n) {
    vector<pair<int, int>> twinPrimes;
    for (int i = 5; i <= n - 2; ++i) {
        if (isPrime(i) && isPrime(i + 2)) {
            twinPrimes.push_back({i, i + 2});
        }
    }
    return twinPrimes;
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;

    vector<pair<int, int>> twinPrimes = findTwinPrimes(n);
    cout << "Các cặp số nguyên tố sinh đôi nhỏ hơn hoặc bằng " << n << " là: " << endl;
    for (auto &pair : twinPrimes) {
        cout << "(" << pair.first << ", " << pair.second << ")" << endl;
    }

    return 0;
}

Cách 2. Sử dụng sàng nguyên tố:

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

// Hàm Sàng Nguyên Tố
void sieve(vector<bool> &isPrime, int maxNum) {
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải là số nguyên tố
    for (int i = 2; i * i <= maxNum; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// Hàm tìm các cặp số nguyên tố sinh đôi nhỏ hơn hoặc bằng n
vector<pair<int, int>> findTwinPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    sieve(isPrime, n);

    vector<pair<int, int>> twinPrimes;
    for (int i = 2; i <= n - 2; ++i) {
        if (isPrime[i] && isPrime[i + 2]) {
            twinPrimes.push_back({i, i + 2});
        }
    }
    return twinPrimes;
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;

    vector<pair<int, int>> twinPrimes = findTwinPrimes(n);
    cout << "Các cặp số nguyên tố sinh đôi nhỏ hơn hoặc bằng " << n << " là: " << endl;
    for (auto &pair : twinPrimes) {
        cout << "(" << pair.first << ", " << pair.second << ")" << endl;
    }

    return 0;
}

Tham khảo:

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

// Hàm sàng tìm các số nguyên tố nhỏ hơn hoặc bằng 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;
}

// Hàm liệt kê các cặp số nguyên tố sinh đôi trong khoảng [1, n]
void findTwinPrimes(int n) {
    vector<bool> isPrime = sieveOfEratosthenes(n);
    int count = 0;

    cout << "Các cặp số nguyên tố sinh đôi trong khoảng [1, " << n << "]:" << endl;
    for (int i = 2; i <= n - 2; ++i) {
        if (isPrime[i] && isPrime[i + 2]) {
            cout << "(" << i << ", " << i + 2 << ")" << endl;
            count++;
        }
    }
    cout << "Tổng số cặp số nguyên tố sinh đôi: " << count << endl;
}

int main() {
    int n = 1000;
    findTwinPrimes(n);
    return 0;
}

Bài tập 8. Tổng các số nguyên tố k nhỏ nhất

Nhập vào một số nguyên k. Viết chương trình tính tổng của k số nguyên tố đầu tiên.
Ví dụ: Với k=5, tổng của 5 số nguyên tố đầu tiên là 2+3+5+7+11=28.

Cách 1. Sử dụng công thức 6k  ± 1:

#include <iostream>
using namespace std;

// Hàm kiểm tra số nguyên tố
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Hàm tính tổng của k số nguyên tố đầu tiên
int sumOfFirstKPrimes(int k) {
    int count = 0, sum = 0, num = 2;
    while (count < k) {
        if (isPrime(num)) {
            sum += num;
            count++;
        }
        num++;
    }
    return sum;
}

int main() {
    int k;
    cout << "Nhập k: ";
    cin >> k;

    int result = sumOfFirstKPrimes(k);
    cout << "Tổng của " << k << " số nguyên tố đầu tiên là: " << result << endl;

    return 0;
}

Cách 2. Sử dụng sàng nguyên tố:

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

// Hàm Sàng Nguyên Tố
void sieve(vector<bool> &isPrime, int maxNum) {
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải là số nguyên tố
    for (int i = 2; i * i <= maxNum; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// Hàm tính tổng của k số nguyên tố đầu tiên
int sumOfFirstKPrimes(int k) {
    int maxNum = 1000000; // Giả sử số nguyên tố nhỏ hơn 1000000
    vector<bool> isPrime(maxNum + 1, true);
    sieve(isPrime, maxNum);

    int count = 0, sum = 0;
    for (int i = 2; i <= maxNum && count < k; ++i) {
        if (isPrime[i]) {
            sum += i;
            count++;
        }
    }
    return sum;
}

int main() {
    int k;
    cout << "Nhập k: ";
    cin >> k;

    int result = sumOfFirstKPrimes(k);
    cout << "Tổng của " << k << " số nguyên tố đầu tiên là: " << result << endl;

    return 0;
}

Số hoàn hảo

Số hoàn hảo là một loại số tự nhiên đặc biệt mà tổng của tất cả các ước số dương thực sự của nó (không kể chính nó) bằng chính nó. Nói cách khác, một số hoàn hảo là số nguyên dương n mà tổng của tất cả các ước số của n (bao gồm cả 1 và n) bằng 2n.

Ví dụ về số hoàn hảo đầu tiên là 6, bởi vì ước số dương của 6 là 1, 2, và 3, và 1 + 2 + 3 = 6.

Bài tập 1. Kiểm tra số hoàn hảo

Viết chương trình kiểm tra xem một số nguyên dương n có phải là số hoàn hảo hay không.

Gợi ý:

  • Tính tổng các ước số thực sự của n (không bao gồm chính nó).
  • So sánh tổng đó với n. Nếu bằng nhau, n là số hoàn hảo.

Code tham khảo:

#include <iostream>
using namespace std;

bool isPerfectNumber(int n) {
    if (n < 2) return false; // Số < 2 không thể là số hoàn hảo
    int sum = 1; // 1 là ước số của mọi số
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum == n;
}

int main() {
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    if (isPerfectNumber(n)) {
        cout << n << " là số hoàn hảo." << endl;
    } else {
        cout << n << " không phải là số hoàn hảo." << endl;
    }

    return 0;
}

Bài tập 2. Liệt kê các số hoàn hảo trong một khoảng

Viết chương trình liệt kê tất cả các số hoàn hảo trong một khoảng cho trước [a,b].

Gợi ý:

  • Duyệt qua từng số trong khoảng [a,b].
  • Sử dụng hàm kiểm tra số hoàn hảo từ Bài tập 1 để kiểm tra từng số.

Code tham khảo:

#include <iostream>
using namespace std;

bool isPerfectNumber(int n) {
    if (n < 2) return false;
    int sum = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum == n;
}

int main() {
    int a, b;
    cout << "Nhập khoảng [a, b]: ";
    cin >> a >> b;

    cout << "Các số hoàn hảo trong khoảng [" << a << ", " << b << "] là: ";
    for (int i = a; i <= b; i++) {
        if (isPerfectNumber(i)) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Bài tập 3. Tìm số hoàn hảo thứ k

Viết chương trình tìm số hoàn hảo thứ k. Biết rằng các số hoàn hảo chẵn có thể được tạo bằng công thức:

n=2p−1×(2p−1)

trong đó 2p−1 là số nguyên tố Mersenne.

Gợi ý:

  • Sử dụng công thức trên để tạo số hoàn hảo.
  • Kiểm tra xem 2p−1 có phải là số nguyên tố không.

Code tham khảo:

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

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

long long findPerfectNumber(int k) {
    int count = 0;
    long long p = 2;
    while (true) {
        long long mersenne = (1LL << p) - 1; // 2^p - 1
        if (isPrime(mersenne)) {
            count++;
            if (count == k) {
                return (1LL << (p - 1)) * mersenne;
            }
        }
        p++;
    }
}

int main() {
    int k;
    cout << "Nhập k: ";
    cin >> k;

    long long perfectNumber = findPerfectNumber(k);
    cout << "Số hoàn hảo thứ " << k << " là: " << perfectNumber << endl;

    return 0;
}

Bài tập 4. Đếm số lượng số hoàn hảo nhỏ hơn N

Viết chương trình đếm số lượng số hoàn hảo nhỏ hơn một số N cho trước.

Gợi ý:

  • Duyệt qua các số từ 2 đến N−1.
  • Sử dụng hàm kiểm tra số hoàn hảo để đếm.

Code tham khảo:

#include <iostream>
using namespace std;

bool isPerfectNumber(int n) {
    if (n < 2) return false;
    int sum = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum == n;
}

int main() {
    int N;
    cout << "Nhập N: ";
    cin >> N;

    int count = 0;
    for (int i = 2; i < N; i++) {
        if (isPerfectNumber(i)) {
            count++;
        }
    }

    cout << "Số lượng số hoàn hảo nhỏ hơn " << N << " là: " << count << endl;

    return 0;
}

Bài tập 5. Tối ưu hóa kiểm tra số hoàn hảo

Cải tiến hàm kiểm tra số hoàn hảo để giảm độ phức tạp thời gian.

Gợi ý:

  • Chỉ duyệt các ước số từ 2 đến sqrt(n)​.
  • Sử dụng tính chất của số hoàn hảo chẵn để tối ưu.

Code tham khảo:

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

bool isPerfectNumber(int n) {
    if (n < 2) return false;
    int sum = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum == n;
}

int main() {
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    if (isPerfectNumber(n)) {
        cout << n << " là số hoàn hảo." << endl;
    } else {
        cout << n << " không phải là số hoàn hảo." << endl;
    }

    return 0;
}

Số thân thiện

Số thân thiện, còn được gọi là số bạn bè, là một cặp các số tự nhiên trong đó tổng của tất cả các ước số thực sự của một số bằng số tự nhiên kia và ngược lại. Dưới đây là một ví dụ về một cặp số thân thiện:

  • Số thứ nhất: 220
    • Ước số của 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110
    • Tổng các ước số trên là: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
  • Số thứ hai: 284
    • Ước số của 284: 1, 2, 4, 71, 142
    • Tổng các ước số trên là: 1 + 2 + 4 + 71 + 142 = 220

Do đó, 220 và 284 là một cặp số thân thiện. Dưới đây là một chương trình tìm tất cả các cặp số thân thiện nhỏ hơn hoặc bằng một số n nhất định:

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

// Hàm tính tổng các ước số thực sự của một số
int sumOfDivisors(int n) {
    int sum = 0;
    for (int i = 1; i <= n / 2; ++i) {
        if (n % i == 0) {
            sum += i;
        }
    }
    return sum;
}

// Hàm tìm các cặp số thân thiện nhỏ hơn hoặc bằng n
vector<pair<int, int>> findFriendlyNumbers(int n) {
    vector<pair<int, int>> friendlyNumbers;
    for (int i = 1; i <= n; ++i) {
        int sum1 = sumOfDivisors(i);
        if (sum1 > i && sum1 <= n) { // Kiểm tra điều kiện tổng các ước lớn hơn i và nhỏ hơn hoặc bằng n
            int sum2 = sumOfDivisors(sum1);
            if (sum2 == i) { // Kiểm tra điều kiện số thân thiện
                friendlyNumbers.push_back({i, sum1});
            }
        }
    }
    return friendlyNumbers;
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;

    vector<pair<int, int>> friendlyNumbers = findFriendlyNumbers(n);
    cout << "Các cặp số thân thiện nhỏ hơn hoặc bằng " << n << " là: " << endl;
    for (auto &pair : friendlyNumbers) {
        cout << "(" << pair.first << ", " << pair.second << ")" << endl;
    }

    return 0;
}

Số Armstrong (Armstrong Numbers)

Số Armstrong (còn gọi là số narcissistic) là một số có n chữ số mà tổng lũy thừa bậc n của từng chữ số bằng chính nó. Ví dụ:

  • 153 là số Armstrong vì 13+53+33=1+125+27=153.
  • 370 là số Armstrong vì 33+73+03=27+343+0=370.

Bài tập 1. Kiểm tra số Armstrong

Viết chương trình kiểm tra xem một số có phải là số Armstrong hay không.

Gợi ý:

  1. Tính số chữ số n của số đó.
  2. Tính tổng lũy thừa bậc n của từng chữ số.
  3. So sánh tổng với số ban đầu.

Code tham khảo:

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

bool isArmstrong(int number) {
    int originalNumber = number;
    int n = 0, sum = 0;

    // Đếm số chữ số
    while (originalNumber != 0) {
        originalNumber /= 10;
        n++;
    }

    originalNumber = number;
    // Tính tổng lũy thừa bậc n của từng chữ số
    while (originalNumber != 0) {
        int digit = originalNumber % 10;
        sum += pow(digit, n);
        originalNumber /= 10;
    }

    return sum == number;
}

int main() {
    int number;
    cout << "Nhập số cần kiểm tra: ";
    cin >> number;

    if (isArmstrong(number)) {
        cout << number << " là số Armstrong." << endl;
    } else {
        cout << number << " không phải là số Armstrong." << endl;
    }

    return 0;
}

Bài tập 2. Liệt kê các số Armstrong trong một khoảng

Viết chương trình liệt kê tất cả các số Armstrong trong một khoảng [a,b].

Gợi ý:

  • Duyệt qua từng số trong khoảng [a,b].
  • Sử dụng hàm kiểm tra số Armstrong từ Bài tập 1 để kiểm tra từng số.

Code tham khảo:

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

bool isArmstrong(int number) {
    int originalNumber = number;
    int n = 0, sum = 0;

    while (originalNumber != 0) {
        originalNumber /= 10;
        n++;
    }

    originalNumber = number;
    while (originalNumber != 0) {
        int digit = originalNumber % 10;
        sum += pow(digit, n);
        originalNumber /= 10;
    }

    return sum == number;
}

int main() {
    int a, b;
    cout << "Nhập khoảng [a, b]: ";
    cin >> a >> b;

    cout << "Các số Armstrong trong khoảng [" << a << ", " << b << "] là: ";
    for (int i = a; i <= b; i++) {
        if (isArmstrong(i)) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Bài tập 3. Tìm số Armstrong có n chữ số

Viết chương trình tìm tất cả các số Armstrong có n chữ số.

Gợi ý:

  • Xác định phạm vi của số có n chữ số (từ 10n−1 đến 10n−1).
  • Sử dụng hàm kiểm tra số Armstrong để tìm các số thỏa mãn.

Code tham khảo:

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

bool isArmstrong(int number, int n) {
    int originalNumber = number;
    int sum = 0;

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

    return sum == number;
}

int main() {
    int n;
    cout << "Nhập số chữ số n: ";
    cin >> n;

    int start = pow(10, n - 1);
    int end = pow(10, n) - 1;

    cout << "Các số Armstrong có " << n << " chữ số là: ";
    for (int i = start; i <= end; i++) {
        if (isArmstrong(i, n)) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Bài tập 4. Đếm số lượng số Armstrong nhỏ hơn N

Viết chương trình đếm số lượng số Armstrong nhỏ hơn một số N cho trước.

Gợi ý:

  • Duyệt qua các số từ 1 đến N−1.
  • Sử dụng hàm kiểm tra số Armstrong để đếm.

Code tham khảo:

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

bool isArmstrong(int number) {
    int originalNumber = number;
    int n = 0, sum = 0;

    while (originalNumber != 0) {
        originalNumber /= 10;
        n++;
    }

    originalNumber = number;
    while (originalNumber != 0) {
        int digit = originalNumber % 10;
        sum += pow(digit, n);
        originalNumber /= 10;
    }

    return sum == number;
}

int main() {
    int N;
    cout << "Nhập N: ";
    cin >> N;

    int count = 0;
    for (int i = 1; i < N; i++) {
        if (isArmstrong(i)) {
            count++;
        }
    }

    cout << "Số lượng số Armstrong nhỏ hơn " << N << " là: " << count << endl;

    return 0;
}

Bài tập 5. Tối ưu hóa kiểm tra số Armstrong

Cải tiến hàm kiểm tra số Armstrong để giảm độ phức tạp thời gian.

Gợi ý: Tính trước số chữ số n và sử dụng nó để tính tổng lũy thừa.

Code tham khảo:

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

bool isArmstrong(int number) {
    int originalNumber = number;
    int n = 0, sum = 0;

    while (originalNumber != 0) {
        originalNumber /= 10;
        n++;
    }

    originalNumber = number;
    while (originalNumber != 0) {
        int digit = originalNumber % 10;
        sum += pow(digit, n);
        originalNumber /= 10;
    }

    return sum == number;
}

int main() {
    int number;
    cout << "Nhập số cần kiểm tra: ";
    cin >> number;

    if (isArmstrong(number)) {
        cout << number << " là số Armstrong." << endl;
    } else {
        cout << number << " không phải là số Armstrong." << endl;
    }

    return 0;
}

CHÚC CÁC BẠN HỌC TỐT!

Đỗ Thành