欧拉筛
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
质数(Prime number)又称素数。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
1既不是质数也不是合数。
题目描述
输入一个正整数n，输出不大于n的自然数中，质数的数量。
输入格式
一个正整数n(1≤n≤10^6)。
输出格式
一个正整数，为不大于n的自然数中，质数的数量。
输入/输出样例
7
4
说明/提示
时间1000ms，内存256MiB