Problem1048--时间复杂度2

1048: 时间复杂度2

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1094  Solved: 750
[Submit] [Status] [Web Board] [Creator:]

Description

给你一个程序:
import math
def f(x): 
    if x == 1: return 0 
    global cnt 
    s = int(math.sqrt(x))
    for i in range(2, s + 1): 
        cnt += 1 
        if x % i == 0: return 1 
    return 2
if __name__ == '__main__': 
    cnt = 0 
    n = int(input())
    for i in range(1, n + 1): f(i) 
    print(cnt)  
每次给定 n, 请求出 cnt 的值。

Input

输入多行数字,以 EOF 结束。 
每一行一个数字 n (1 ≤ n ≤ 10000) 表示题意中的 n 。 

Output

对于每一行的 n 输出对应值。

Sample Input

10

Sample Output

8

Source/Category


[Submit] [Status]