题目描述
【题目描述】
继上次鲍勃在排序算法的研究上遭遇失败之后，这次他开始研究数论问题。他学习了欧拉函数的定 义：ϕ(n) 等于小于等于 n 的与 n 互质的正整数的个数。
鲍勃又发现了一种神奇的数字，这些数字 x 满足 ϕ(x) 的最大质因子不超过 5。
鲍勃想让你帮忙计算一下，1 ∼n 内神奇数字的和是多少？由于答案过大，请你输出答案对 2^32 取模后的值
【输入格式】
第一行一个整数 n(1 ≤ n ≤ 10^12)，代表题目中的范围。
【输出格式】
对于每组数据，输出一行一个答案，代表 1 ∼n 内神奇数字的和。对 2^32 取模后的值
样例
|
math.in
|
math.out
|
|
1000000000000
|
939087315
|
|
23
|
253
|
【数据范围与约束】
共 10 组数据
|
测试点
|
n ≤
|
|
第 i 组数据
|
10^(i+2)
|
【提示】
第一个不神奇的数字是 23，ϕ(23) = 22 = 2 ∗ 11