Tuần 5

Số nguyên tố và sàng

Độ khó: ★★★☆☆ Vừa
Thời lượng: Khoảng 90 phút
Học trước: Ước, bội, ƯCLN, BCNN
Chủ đề: số họcsố nguyên tố
Trạng thái

Kiến thức cơ bản

Số nguyên tố, hợp số

Số nguyên tố là số nguyên lớn hơn 1 có đúng hai ước nguyên dương là 1 và chính nó. Các số nguyên tố nhỏ hơn 100 gồm: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Hợp số là số tự nhiên lớn hơn 1 và có nhiều hơn hai ước dương. Ví dụ: số 6 là hợp số vì nó có 4 ước dương 1, 2, 3, 6.

Chú ý rằng, hai số 0 và 1 không phải số nguyên tố, cũng không là hợp số. Số 2 là số nguyên tố chẵn duy nhất.

Kiểm tra số nguyên tố

Để kiểm tra số nguyên n > 1 có phải là số nguyên tố không, ta kiểm tra nếu tồn tại một số nguyên i (2 ≤ i ≤ sqrt(n)) mà i là ước của n thì n không phải là số nguyên tố, ngược lại n là số nguyên tố.

// Hàm trả về true nếu n là số nguyên tố, ngược lại trả về false
bool isPrime(ll n) {
    if (n <= 1) return false;
    for (ll i = 2; i*i <= n; ++i) // i*i <= n là i<=sqrt(n)
        if (n%i == 0) return false;
    return true;
}

Một cách hiệu quả hơn, dựa trên điều kiện mọi số nguyên được biểu thị dưới dạng 6k, 6k+1, 6k+2, 6k+3, 6k+4 và 6k+5 mà 6k, 6k+2, 6k+4 chia hết cho 2 còn 6k+3 chia hết cho 3 nên số nguyên tố lớn hơn 3 đều có dạng 6k±1. Vì vậy, ta chỉ cần kiểm tra xem n có chia hết cho 2 hay 3 không, sau đó kiểm tra tất cả các số có dạng 6k ± 1 ≤ sqrt(n).

bool isPrime(ll n) {
    if(n == 2 || n == 3) return true;
    if(n < 2 || 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;
}

Phân tích ra thừa số nguyên tố

Mọi số lớn hơn 1 đều viết được duy nhất (không kể thứ tự) thành tích các số nguyên tố. Ví dụ: 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³.3².5. Mỗi số nguyên tố kèm số mũ của nó gọi là một thừa số nguyên tố.

Ý tưởng là duyệt bắt đầu từ ước i = 2, trong khi n ⋮ i thì ta bổ sung i vào kết quả, và tăng i đến khi gặp n ⋮ i thì i là thừa số nguyên tố tiếp theo. Khi đã loại hết các ước i*i ≤ n mà n >1 thì n là số nguyên tố, ta bổ sung n vào kết quả.

// In ra cách phân tích n ra thừa số nguyên tố
void factorize(int n) {
    for(int i = 2; i*i <= n; ++i) {
        while(n%i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
    if(n > 1) cout << n << " ";
}

Khi phân tích n ra thừa số nguyên tố kèm số mũ, ta sử dụng code sau:

void factorize(int n) {
    for(int p = 2; p*p <= n; ++p) {
        if(n%p == 0){
            int e = 0;
            while(n%p == 0) {
                ++e; n /= p;
            }
            cout <<p; if(e>1)  cout <<"^" <<e;
            if(n>1) cout <<"*";
        }
    }
    if(n > 1) cout <<n;
}

Ứng dụng đếm ước: Giả sử n được phân tích ra thừa số nguyên tố thành n = , khi đó số ước của n là: (e₁+1).(e₂+1)...(e_k+1);

Sàng Eratosthenes

Thuật toán sàng số nguyên tố Eratosthenes như sau: lập bảng các số có giá trị từ 2 đến n; số đầu tiên 2 là số nguyên tố, loại tất cả các bội của 2; số còn lại tiếp theo là 3, loại tất cả các bội của 3;... tiếp tục khi số còn lại tiếp theo lớn hơn sqrt(n). Tất cả các số còn lại là số nguyên tố.

#include <iostream>
using namespace std;

const int maxN = 1e7;
bool prime[maxN+1];

void sieve() {
    prime[0] = 1; prime[1] = 1;
    for(int i = 2; i*i <= maxN; ++i) if(!prime[i])
        for(int j = i*i; j <= maxN; j += i) prime[j] = 1;
}

int main() {
    sieve();
    int n; cin >> n;
    for(int i = 2; i <= n; ++i)
        if(!prime[i]) cout <<i <<' ';

    return 0;
}

Luyện tập

Bài 1. Kiểm tra số nguyên tố

Cô giáo viết lên bảng một số n và hỏi cả lớp: "Số này có phải số nguyên tố không?". Bạn hãy viết chương trình trả lời thật nhanh, kể cả khi n rất lớn nhé!

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10⁹)
Đầu ra	In YES nếu n là số nguyên tố, ngược lại in NO.
	29	YES
	91	NO

Bài 2. Liệt kê số nguyên tố

Bạn Gấu muốn lập danh sách các số nguyên tố để trang trí bảng tin lớp. Vì biết lập trình nên Gấu đã viết chương trình in ra tất cả số nguyên tố không vượt quá n.

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10⁵)
Đầu ra	Các số nguyên tố từ 2 đến n theo thứ tự tăng dần, cách nhau một dấu cách.
	30	2 3 5 7 11 13 17 19 23 29

Bài 3. Đếm số nguyên tố trong đoạn

Trường học của Hùng có các phòng học đánh số từ l đến r. Phòng có số nguyên tố được sơn màu xanh. Hãy đếm xem có bao nhiêu phòng được sơn xanh.

Test	Input	Output
Đầu vào	Hai số nguyên l, r (1 ≤ l ≤ r ≤10⁵)
Đầu ra	Số lượng số nguyên tố trong đoạn từ l đến r
	10 30	6

Bài 4. Phân tích thừa số nguyên tố

Người ngoài hành tinh nói rằng mọi con số đều được xây từ các "viên gạch nguyên tố". Hãy cho họ biết số n được xây từ những viên gạch nào và mỗi loại dùng bao nhiêu viên (số mũ).

Test	Input	Output
Đầu vào	Một số nguyên n (2 ≤ n ≤10¹²)
Đầu ra	Mỗi thừa số nguyên tố trên một dòng: số nguyên tố và số mũ, cách nhau một dấu cách, theo thứ tự tăng dần.
	360	2 3 3 2 5 1

Bài 5. Đếm ước từ thừa số nguyên tố

Cô giáo hỏi: "Số n có bao nhiêu ước?". Bạn hãy trả lời bằng cách phân tích n ra thừa số nguyên tố rồi dùng công thức (e1+1).(e2+1). ... với e1, e2, ... là các số mũ.

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10¹²)
Đầu ra	Số lượng ước của n.
	360	24
	600851475143	16

Bài 6. Số Sphenic

Một số nguyên dương n được gọi là số Sphenic nếu nó được tạo thành từ tích của đúng 3 số nguyên tố khác nhau (n = p.q.r với p≠q≠r). Ví dụ: 30 = 2.3.5 là số Sphenic; nhưng 60 = 2.2.3.5 không phải vì có 4 ước nguyên tố và bị trùng số 2.

Cho số n, hãy kiểm tra xem n có phải là số Sphenic không!

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10⁹)
Đầu ra	In ra YES nếu n là số Sphenic, ngược lại in ra NO.
	30	YES
	12	NO

Bài 7. Số Smith kỳ diệu

Số Smith là một hợp số mà tổng các chữ số của nó bằng đúng tổng các chữ số của tất cả các thừa số nguyên tố cấu tạo nên nó. Ví dụ 85 là số Smith vì 8+5 = 13 và khi phân tích ra thừa số nguyên tố 85 = 5.17 có 5+1+7 = 13.

Hãy kiểm tra xem số n có phải là số Smith không nhé!

Test	Input	Output
Đầu vào	Một số nguyên n (2 ≤ n ≤10⁹)
Đầu ra	In ra YES nếu n là số Smith, ngược lại in ra NO
	85	YES
	12	NO

Bài 8. Số nguyên tố đối xứng

Một số được gọi là "nguyên tố đối xứng" nếu nó vừa là số nguyên tố, vừa đọc xuôi hay ngược đều như nhau (ví dụ 11, 101, 131). Hãy đếm xem có bao nhiêu số nguyên tố đối xứng không vượt quá n.

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10⁶)
Đầu ra	Số lượng số nguyên tố đối xứng không vượt quá n.
	100	5

Bài 9. Số gần nguyên tố

Một số nguyên dương được gọi là "Gần nguyên tố" nếu nó có đúng hai ước số nguyên tố khác nhau (Ví dụ: 6 = 2.3, 18 = 2.3², 20 = 2².5 đều có đúng 2 ước nguyên tố ). Hãy đếm xem từ 1 đến n có bao nhiêu số gần nguyên tố!

Test	Input	Output
Đầu vào	Một số nguyên dương n (1 ≤ n ≤ 3000)
Đầu ra	Số lượng số gần nguyên tố trong khoảng từ 1 đến n
	10	2 Giải thích: hai số thoả mãn là 6 = 2.3, 10 = 2.5.

Bài 10. Đếm số nguyên tố trong đoạn [l, r]

Bác thợ mỏ muốn đếm xem trên đoạn đường ray từ cột mốc L đến cột mốc R có bao nhiêu cột mốc được đánh số nguyên tố. Vì bác có rất nhiều đoạn cần hỏi nên em hãy tính toán thật nhanh nhé!

Test	Input	Output
Đầu vào	Dòng 1: Số truy vấn q (1 ≤ q ≤10⁵); q dòng tiếp theo, mỗi dòng chứa hai số l, r (1 ≤ l ≤ r ≤ 10⁶)
Đầu ra	Với mỗi truy vấn, in ra số lượng số nguyên tố trong đoạn [l, r]
	3 1 10 3 5 10 20	4 2 4

Bài tập tự luyện

Bài 1. Cặp số nguyên tố sinh đôi

Hai số nguyên tố hơn kém nhau đúng 2 đơn vị (như 3 và 5, hay 11 và 13) được gọi là cặp số nguyên tố sinh đôi. Hãy đếm số cặp (p, p + 2) mà cả hai số đều là số nguyên tố và p + 2 không vượt quá n.

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10⁶)
Đầu ra	Số cặp số nguyên tố sinh đôi không vượt quá n
	100	8

Bài 2. Tổng hai số nguyên tố

Giả thuyết Goldbach cho rằng mọi số chẵn lớn hơn 2 đều viết được thành tổng của hai số nguyên tố. Cho số chẵn n, hãy tìm cách viết n = p + q với p ≤ q, p nguyên tố, q nguyên tố và p nhỏ nhất có thể.

Test	Input	Output
Đầu vào	Một số chẵn n (4 ≤ n ≤10⁶)
Đầu ra	Hai số p và q cách nhau một dấu cách
	10	3 7
	28	5 23

Bài 3. Tổng chữ số cũng nguyên tố

Số nguyên tố "kép" là những số mà bản thân nó là số nguyên tố và tổng các chữ số của nó cũng là số nguyên tố (ví dụ 23 có tổng chữ số 2 + 3 = 5). Hãy đếm các số như vậy không vượt quá n.

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10⁶)
Đầu ra	Số lượng số nguyên tố không vượt quá n mà tổng chữ số cũng là số nguyên tố
	30	7

Bài 4. Khoảng trống lớn nhất

Trong các số nguyên tố không vượt quá n, hãy tìm khoảng cách lớn nhất giữa hai số nguyên tố liên tiếp. Ví dụ các số nguyên tố không vượt quá 10 là 2, 3, 5, 7 và các khoảng cách là 1, 2, 2.

Test	Input	Output
Đầu vào	Một số nguyên n (3 ≤ n ≤10⁶)
Đầu ra	Khoảng cách lớn nhất giữa hai số nguyên tố liên tiếp không vượt quá n
	30	6

Bài 5. Số có đúng 3 ước

Hãy kiểm tra xem số n có đúng 3 ước hay không?

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10¹²)
Đầu ra	In YES nếu n có đúng 3 ước, ngược lại in NO
	49	YES
	36	NO

Bài 6. Nhiều câu hỏi về số ước

Panda nhận được q câu hỏi, mỗi câu cho một số x và hỏi x có bao nhiêu ước. Với q lớn, phân tích từng số bằng cách thử chia sẽ chậm.

Test	Input	Output
Đầu vào	Dòng 1: số nguyên q (1 ≤ q ≤10⁵) . Dòng 2: q số nguyên x (1 ≤ x ≤10⁶)
Đầu ra	Với mỗi số x, in số lượng ước của x trên một dòng.
	3 12 36 97	6 9 2

Bài 7. Số nguyên tố thứ k

Dãy số nguyên tố là 2, 3, 5, 7, 11, ... Hãy cho biết số nguyên tố thứ k.

Test	Input	Output
Đầu vào	Một số nguyên k (1 ≤ k ≤ 50000)
Đầu ra	Số nguyên tố thứ k
	1	2
	10	29
	50000	611953

Bài 8. Những bạn thân của n

Đếm các số từ 1 đến n nguyên tố cùng nhau với n, n có thể lên tới 10¹².

Test	Input	Output
Đầu vào	Một số nguyên n (1 ≤ n ≤10¹²)
Đầu ra	Số lượng số trong đoạn từ 1 đến n nguyên tố cùng nhau với n
	10	4
	360	96

Gợi ý: Nếu phân tích ra thừa số nguyên tố của , thì số số nguyên tố cùng nhau với n trong đoạn từ 1 tới n được tính bởi phi hàm Euler:

Bài 9. Ước nguyên tố thứ k

Cho hai số n và k, in ra thừa số nguyên tố phân biệt thứ k trong số tất cả các ước nguyên tố của n. Ví dụ, n= 15, k= 2, kết quả là 5. Nếu n= 15, k= 3, thì kết quả là "-1" (số ước nguyên tố <k).

Test	Input	Output
Đầu vào	Hai số nguyên n, k (1 ≤ n, k ≤10⁹)
Đầu ra	Thừa số nguyên tố phân biệt thứ k của n
	15 2	5
	15 3	-1

Hướng dẫn: Thực hiện phân tích n ra thừa số nguyên tố, và theo dõi biến đếm cnt. Nếu cnt = k, trả về thừa số nguyên tố hiện tại. Trả về -1 nếu không tìm thất thừa số nguyên tố thứ k.

Bài 10. Tìm các số có n ước

Cho ba số nguyên a, b, n. Hãy in ra số lượng các số thuộc đoạn [a, b] có n ước số. Ví dụ a = 1, b = 7, n = 2 thì kết quả là 4 (có 4 số có 2 ước là: 2, 3, 5, 7).

Test	Input	Output
Đầu vào	Ba số nguyên a, b, n (1 ≤ a, b, n ≤10⁶)
Đầu ra	Số lượng các số thuộc đoạn [a, b] có n ước số
	1 7 2	4

Hướng dẫn: Duyệt i từ a đến b và để so sánh số ước của i với n. Để thuật toán hiệu quả, tính trước mảng cntDiv[i] (lưu số ước của i) để so sánh.

Ghi chú cá nhân (lưu trên trình duyệt này)

Bài liên quan

Tuần 4Ước, bội, ƯCLN, BCNN