|
|
SPOJ Problem Set (classical)
4168. Square-free integers
Problem code: SQFREE
|
In number theory we call an integer square-free if it is not divisible by a perfect square, except 1. You have to count them!
Input
First line contains an integer T, the number of test cases (T≤100).
The following T lines each contains one positive integer: n, where n ≤ 1014
Output
T lines, on each line output the number of (positive) square-free integers not larger than n.
Example
Input:
3
1
1000
100000000000000
Output:
1
608
60792710185947
Warning: A naive algorithm probably not works.
| Added by: | Robert Gerbicz |
| Date: | 2009-04-06 |
| Time limit: | 20s
|
| Source limit: | 2009B |
| Languages: | All except: ERL JS |
| Resource: | classic, own input |
|
|
|
|
RSS