Bedao Regular Contest 17 - Lona và số nguyên tố

View as PDF
Submit solution
Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ngày mai lớp của ~Lona~ sẽ có buổi kiểm tra Tin học. ~Lona~ rất lo lắng vì đề thầy cho rất khó và hại não. Do đó để có thể được thêm điểm cộng cho bài kiếm tra này thì ~Lona~ đã quyết định sẽ xung phong giải bài tập về nhà.

Thầy giáo cho các bạn trong lớp một số nguyên dương ~n~ và yêu cầu đếm tất cả các số nguyên dương ~s~ thỏa mãn:

  • ~s \le n~
  • ~s = p^3 \times q^3~ với ~p~ và ~q~ là các số nguyên tố phân biệt.

Loay hoay mãi nhưng ~Lona~ vẫn chưa thể giải được nên đành nhờ các bạn ở ~VNOJ~ giúp đỡ. Là một lập trình thiên tài, bạn hãy giúp đỡ ~Lona~ nhé.

Input

Dòng duy nhất nhập vào một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~.

Output

In ra yêu cầu đề bài: số số nguyên dương ~s~ thỏa mãn.

Scoring

Subtask Điểm Giới hạn
1 ~50~ ~n \le 10 ^ 6~
2 ~50~ Không có điều kiện gì thêm

Sample Input 1

1000

Sample Output 1

2

Notes

Có ~2~ số thỏa mãn đề bài:

  • ~216 = 2^3 \times 3^3~
  • ~1000 = 2^3 \times 5^3~

Comments

Please read the guidelines before commenting.