Sàng số nguyên tố

Bạn có một số nguyên dương \(N\). Nhiệm vụ của bạn là xuất ra tất cả các số nguyên tố từ \(1\) tới \(N\).

Input

• Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N \leq 10^6)\).

Output

• Xuất ra tất cả các số nguyên tố từ \(1\) tới \(N\) trên cùng một dòng và cách nhau một dấu cách.

Example

10 

2 3 5 7

Số nguyên dương \(x\) được gọi là một ước nguyên tố của số nguyên \(k\) nếu \(k\) chia hết cho \(x\) và \(x\) là số nguyên tố.

Yêu cầu: Nhập từ bàn phím một số nguyên dương \(k\). Hãy in ra màn hình tổng các ước nguyên tố của số \(k\).

Dữ liệu

• Số nguyên dương \(k\)

Kết quả

• Tổng các ước nguyên tố của số \(k\)

Input

21

Output

10

Ràng buộc

• Sub1: 70% test: \(k\le 10^{10}\) theo đề chuẩn
• Sub2: 30% test: \(k\le 10^{16}\) mở rộng

Nguồn: Bài 1 TS10 LQĐ TPĐN '2014

Nhập số nguyên dương \(N\). Hãy in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng \(N\) theo thứ tự tăng dần.

Input

• Nhập số nguyên dương \(N\) (\(1 \leq N \leq 10^6\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

4

2 3

13

2 3 5 7 11 13

Nhập \(2\) số nguyên dương \(A, B\). In ra các số nguyên tố trong khoảng từ \(A\) đến \(B\) (chú ý lấy cả \(2\) cận \(A\), \(B\)).

Input

• Nhập \(2\) số nguyên dương \(A, B\) (\(1 \leq A \leq B \leq 10^6\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

4 20

5 7 11 13 17 19

1 5

2 3 5

Hãy đếm số lượng thừa số nguyên tố khác nhau trong phân tích thừa số nguyên tố của \(1\) số nguyên dương \(n\).

Input

• Dòng đầu tiên là số lượng test case \(T\ (1 \le T \le 100)\).
• \(T\) dòng tiếp theo mỗi dòng là một số nguyên dương \(n\ (1 \le n \le 10^9)\).

Output

• Với mỗi dòng, đưa ra một số nguyên là số lượng thừa số nguyên tố khác nhau của \(n\).

Example

3
60
128
10000

3
1
2