Cho N là số nguyên nhỏ hơn hoặc bằng 10^6

Tìm ước nguyên tố lớn nhất xuất hiện trong N!

Đầu vào: Nhập số nguyên N (2 < N <= 10^6)

Đầu ra: In ra số nguyên tố lớn nhất xuất hiện trong N!

Input 01:

10

Output 01:

7

Input 02:

999999

Output 02:

999983

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

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

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

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

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))

Cho T truy vấn. Với mỗi số X, hãy in ra phân tích thừa số nguyên tố của X dưới dạng p1^a1 x p2^a2 x ... Yêu cầu: Dùng Sàng để tìm Ước SNT Nhỏ Nhất (SPF - Smallest Prime Factor) để tăng tốc độ phân tích.

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à chuỗi phân tích. (Xem ví dụ).

Test Case 1:

Input:

3
12
13
28

Output:

2^2 x 3^1
13^1
2^2 x 7^1

Cho N. Tìm số i (1 <= i <= N) có số lượng ước số lớn nhất. Nếu có nhiều số i có cùng số lượng ước lớn nhất, hãy in ra số i nhỏ nhất. Gợi ý: Nếu n = p1^a1 x p2^a2, thì d(n) = (a1+1) x (a2+1).

Input:

Một dòng duy nhất chứa số nguyên N (1 <= N <= 100000).

Output:

In ra số i có nhiều ước nhất.

Test Case 1:

Input:

10

Output:

6

(Giải thích: 6, 8, 10 đều có 4 ước. Chọn 6 vì nhỏ nhất)

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})

Cho số nguyên dương N ≤ 10^6.

Với mỗi số nguyên dương i (1 ≤ i ≤ N), hãy đếm:

1. Số ước chẵn của i.

2. Số ước lẻ của i.

3. Số ước của i mà bản thân ước đó là số nguyên tố.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra:

In ra N dòng, mỗi dòng chứa 3 số nguyên, cách nhau bởi một dấu cách

evencount[i] oddcount[i] prime_count[i]

trong đó:

• even_count [il là số ước chẵn của i,

• odd_count [il là số ước lẻ của i,

• prime_count [il là số ước nguyên tố của i.

Ví dụ:

Input 01:

6

Output 01:

0 1 0
1 1 1
0 2 1
2 1 1
0 2 1
2 2 2

Cho một số nguyên dương N ≤ 10^6.

Hãy tính tổng các ước của mỗi số nguyên dương từ 1 đến N.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra: In ra N dòng, dòng thứ i chứa tổng các ước của số i.

Ràng buộc: 1 ≤ N < 10^6

Ví dụ:

Input:

6

Output:

1
3
4
7
6
12

Cho một số nguyên dương N ≤ 10^6.

Hãy tìm tất cả các số trong đoạn [1..N] có số lượng ước nhiều nhất.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra:

• Dòng đầu tiên: in số lượng ước lớn nhất.

• Dòng thứ hai: in các số trong đoạn [1..N] có đúng số lượng ước đó, theo thứ tự tăng dần, cách nhau bởi một dấu cách.

Input 01:

6

Output 01:

4
6

Input 02:

10

Output 02:

4
6 8 10

Giải thích: Các số 6, 8, 10 là các số có số lượng ước lớn nhất (=4) trong khoảng từ 1 đến 10

Cho một số nguyên dương N ≤ 10^6.

Hãy tính tổng tất cả các ước của mọi số từ 1 đến N.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra: In ra một số duy nhất là tổng của tất cả các ước của các số từ 1 đến N.

Input:

6

Output:

33

Tổng các ước của các số từ 1 đến 6 là: 1 + 3 + 4 + 7 + 6 + 12 = 33

Cho một số nguyên dương N ≤ 10^6

Hãy tính tổng các ước lẻ hoặc tổng các ước chẵn của mọi số từ 1 đến N.

Dữ liệu vào: Một dòng duy nhất chứa hai giá trị: N K

Trong đó:

• N là số nguyên dương (1 ≤ N ≤ 10^6)

• K là ký tự 'L' hoặc 'C':

'L' nghĩa là tính tổng các ước lẻ

'C' nghĩa là tính tổng các ước chẵn

Dữ liệu ra: In ra một số duy nhất — là tổng của tất cả các ước lẻ (hoặc chẵn) của các số từ 1 đến N.

Input 01:

6 L

Output 01:

17

Input 02:

6 C

Output 02:

16

Sử dụng kỹ thuật sàng để phân tích thừa số nguyên tố cho Q số nguyên n. Với mỗi số, in ra các thừa số nguyên tố theo thứ tự tăng dần.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau, mỗi dòng chứa n.

Dữ liệu ra: Q dòng, mỗi dòng chứa các thừa số nguyên tố của n cách nhau bởi dấu cách.

Ràng buộc: 1 <= Q <= 100000; 2 <= n <= 1000000

Ví dụ 1:

Input:

2 
12 
10

Output:

2 2 3 
2 5

Ví dụ 2:

Input:

2 
7 
18

Output:

7 
2 3 3