Sàng Nguyên Tố Eratosthenes Trên Đoạn [1..N]

Buổi 57 — Sàng & Euler Totient Mathematics Number Theory
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho số nguyên dương N (1 ≤ N ≤ 10^6). Hãy đếm số lượng số nguyên tố không vượt quá N.

Dữ liệu vào (Input)
  • Một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10^6).
Dữ liệu ra (Output)
  • In ra một số nguyên duy nhất là số lượng số nguyên tố trong đoạn [1..N].
Ví dụ mẫu
Sample Input 1
10
Sample Output 1
4
Sample Input 2
100
Sample Output 2
25
Draft saved