8562: Fourier and Theory for the Universe

内存限制:128 MB 时间限制:3 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:1

题目描述

Note: the description is really long. For better understanding, important conceptions are in bold style.

Fourier has started a project with his friends, aiming to research into the ultimate theory for the whole universe.

Georg Cantor, the trailblazer in set theory, uses 'Marvelous Cantor Set(MCS)' to describe the universe. In plain language, the MCS contains all the integers from 1 to n.

René Descartes, who has invented a lot of important operators, uses 'Profound Descartes Operator(PCO)' to describe how the elements in MCS interact with each other. In plain language, when PCO is exerted on exactly two elements in MCS, the product of the two elements shall be returned. Moreover, the PCO is only defined between two numbers with product no more than n.

Leonhard Euler, the master of number theory, has discovered the fundamental elements in MCS. He names them 'Fabulous Euler Number(FEN)'. In his research, he finds that all the PCOs of two different prime numbers, are FEN.

George Boole, the pioneer in boolean logistic, has perfected the definition of FEN. He uses 'Excellent Boole Law(EBL)' for it, which contains two descriptions:

  • the PCO of two FENs are FEN, as long as the PCO between them is defined. Note that the two FENs can be the same.
  • no other numbers than all the PCOs of two different prime numbers and the PCOs of two FENs, are FENs.

Through hundreds and thousands of great scientists' investigations, the algebra in MCS has finally be fulfilled. However, the law of converting of normal natural numbers to elements in MCS hasn't been found, and in long time periods, MCS algebra was not widely used.

Finally, Fourier, the genius transformation researcher, advanced 'Final Fourier Transformation(FFT)' for this problem. The theorem is an epochal discovery, although with a small flaw: FFT requires to count the number of FENs in MCS, however Fourier doesn't know how to do it!

Help Fourier with this problem! If you can solve it successfully, there may be a constant named after you!

输入格式


One line with a single number, n(1≤n≤1e11)

输出格式


One line with a single number, which is the number of FENs in MCS.

输入样例 复制

10

输出样例 复制

2

数据范围与提示

In this case, only 6 and 10 are FENs.

分类标签