Sàng số nguyên tố cơ bản
In ra các số nguyên tố từ 1 đến n (sàng số nguyên tố)
Nộp bàiPoint: 1
In ra các số nguyên tố từ 1 đến n sử dụng sàng số nguyên tố
Ràng buộc: n đến 10^6
Input 01:
10
Output 01:
2 3 5 7
Input 02:
100
Output 02:
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
Số nguyên tố trong đoạn
Nộp bàiPoint: 1
Viết chương trình cho phép nhập vào hai số nguyên dương và tìm tất cả các số nguyên tố nằm trong khoảng đó.
INPUT:
10 50
OUTPUT:
11 13 17 19 23 29 31 37 41 43 47
Đếm số lượng số nguyên tố nhỏ hơn N
Nộp bàiPoint: 1
Cho số nguyên dương N ≤ 10^6. Hãy đếm có bao nhiêu số nguyên tố nhỏ hơn hoặc bằng N.
Input:
10
Output:
4
Đếm Số Nguyên Tố Trong Khoảng
Nộp bàiPoint: 1
Cho một số nguyên N và Q truy vấn. Mỗi truy vấn gồm hai số L và R. Hãy đếm xem có bao nhiêu số nguyên tố p sao cho L <= p <= R.
Input:
Dòng đầu tiên chứa hai số nguyên N và Q (1 <= N <= 1000000, 1 <= Q <= 100000).
Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 <= L <= R <= N).
Output:
In ra Q dòng, mỗi dòng là số lượng số nguyên tố trong đoạn [L, R] tương ứng.
Test Case 1:
Input:
10 2
1 5
6 10
Output:
3
1
(Giải thích: [1, 5] có {2, 3, 5}. [6, 10] có {7})
Test Case 2:
Input:
30 3
10 20
25 30
1 1
Output:
4
1
0
Tổng Của Tất Cả SNT
Nộp bàiPoint: 1
Cho một số nguyên N. Hãy tính tổng của tất cả các số nguyên tố nhỏ hơn hoặc bằng N.
Input:
Một dòng duy nhất chứa số nguyên N (2 <= N <= 1000000).
Output:
In ra tổng của các số nguyên tố. (Lưu ý: kết quả có thể vượt quá 32-bit, hãy dùng long long trong C++ hoặc long trong Java/Python).
Test Case 1:
Input:
10
Output:
17
(Giải thích: 2 + 3 + 5 + 7 = 17)
Test Case 2:
Input:
30
Output:
129
Số Nguyên Tố Thứ K
Nộp bàiPoint: 1
Tìm số nguyên tố thứ K. (Số nguyên tố thứ 1 là 2, thứ 2 là 3, ...)
Input:
Một dòng duy nhất chứa số nguyên K (1 <= K <= 78498). (Giới hạn K đảm bảo SNT thứ K sẽ <= 1000000).
Output:
In ra số nguyên tố thứ K.
Test Case 1:
Input:
5
Output:
11
SNT Cặp (Twin Primes)
Nộp bàiPoint: 1
Một cặp SNT sinh đôi là một cặp số nguyên tố (p, p+2). Cho một số nguyên N. Hãy đếm số lượng cặp SNT sinh đôi (p, p+2) sao cho p+2 <= N.
Input:
Một dòng duy nhất chứa số nguyên N (5 <= N <= 1000000).
Output:
In ra số lượng cặp SNT sinh đôi thỏa mãn.
Test Case 1:
Input:
15
Output:
3
(Giải thích: Các cặp là (3, 5), (5, 7), (11, 13))
Goldbach Phân Tích (Đơn giản)
Nộp bàiPoint: 1
Giả thuyết Goldbach cho rằng mọi số chẵn lớn hơn 2 đều là tổng của hai số nguyên tố. Cho T truy vấn, mỗi truy vấn là một số chẵn X. Hãy tìm một cặp SNT (p, q) sao cho p + q = X. Nếu có nhiều cặp, hãy in cặp có p nhỏ nhất.
Input:
Dòng đầu tiên chứa T (1 <= T <= 100000).
T dòng tiếp theo, mỗi dòng chứa một số chẵn X (4 <= X <= 1000000).
Output:
T dòng, mỗi dòng in ra hai số nguyên tố p và q (p <= q), cách nhau bởi dấu cách.
Test Case 1:
Input:
2
8
10
Output:
3 5
3 7
Test Case 2:
Input:
2
16
22
Output:
3 13
3 19
(Giải thích 22: 3+19, 5+17, 11+11. Chọn 3 19 vì 3 là p nhỏ nhất)
SNT Có Tổng Chữ Số Là SNT
Nộp bàiPoint: 1
Một số nguyên tố p được gọi là "SNT Đặc Biệt" nếu tổng các chữ số của nó cũng là một số nguyên tố. Cho N. Hãy đếm số lượng SNT Đặc Biệt nhỏ hơn hoặc bằng N.
Input:
Một dòng duy nhất chứa số nguyên N (2 <= N <= 1000000).
Output:
In ra số lượng SNT Đặc Biệt.
Test Case 1:
Input:
30
Output:
7
(Giải thích: SNT <= 30: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. Tổng chữ số: {2, 3, 5, 7, 2, 4, 8, 10, 5, 11}. Các SNT có TCS là SNT: {2, 3, 5, 7, 11, 23, 29} -> 7 số)
Số Chỉ Có Một Ước SNT
Nộp bàiPoint: 1
Một số i > 1 được gọi là "số lũy thừa" nếu nó chỉ có duy nhất một ước nguyên tố. (Ví dụ: 8 = 2^3, 9 = 3^2, 5 = 5^1). Cho N. Hãy đếm số lượng "số lũy thừa" i (1 < i <= N).
Input:
Một dòng duy nhất chứa số nguyên N (2 <= N <= 1000000).
Output:
In ra số lượng số lũy thừa.
Test Case 1:
Input:
20
Output:
12
(Giải thích: {2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19})
Đếm Số Lượng Ước SNT Khác Nhau
Nộp bàiPoint: 1
Cho T truy vấn. Với mỗi số X, hãy đếm số lượng ước nguyên tố khác nhau của X. Ví dụ: 12 = 2^2 x 3 có 2 ước SNT khác nhau là {2, 3}. 30 = 2 x 3 x 5 có 3 ước.
Input:
Dòng đầu tiên chứa T (1 <= T <= 100000).
T dòng tiếp theo, mỗi dòng chứa một số nguyên X (2 <= X <= 1000000).
Output:
T dòng, mỗi dòng là số lượng ước SNT khác nhau của X.
Test Case 1:
Input:
3
12
17
30
Output:
2
1
3
Test Case 2:
Input:
2
48
50
Output:
2
2
(Giải thích: 48 = 2^4 x 3; 50 = 2 x 5^2)
Số Bán Nguyên Tố (Semi-Prime)
Nộp bàiPoint: 1
Một số được gọi là Bán Nguyên Tố nếu nó là tích của đúng hai số nguyên tố (hai số này có thể bằng nhau). Ví dụ: 4 = 2 x 2, 6 = 2 x 3, 9 = 3 x 3, 10 = 2 x 5. Cho N. Hãy đếm số lượng số Bán Nguyên Tố <= N.
Input:
Một dòng duy nhất chứa số nguyên N (1 <= N <= 1000000).
Output:
In ra số lượng số Bán Nguyên Tố nhỏ hơn hoặc bằng N.
Test Case 1:
Input:
20
Output:
6
(Giải thích: {4, 6, 9, 10, 14, 15})