SPOJ.com - Problem SQFREE

SQFREE - Square-free integers

#number-theory

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!

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 ≤ 10¹⁴

T lines, on each line output the number of (positive) square-free integers not larger than n.

Input:
3
1
1000
100000000000000

Output:
1
608
60792710185947

Warning: A naive algorithm will probably not be sufficient to be accepted.

< Previous 1 2 Next >

	f_rank_coder1: 2024-10-17 10:33:19 yay, solved in atmost O(T*6079290)
	serendipity97: 2019-11-17 14:40:07 O(Tsqrt(n)) passes!!
	leokery: 2017-11-01 14:44:13 A naive algorithm
	xiaoyimi: 2017-01-05 03:53:18 It's so crazy! I don't think this problem can be accepted by O(T√n)!
	cccsober: 2016-06-26 13:11:40 mobius is enough...
	Scape: 2015-09-21 15:53:07 nlogn is sufficient to get Accepted.
	Who: 2014-11-25 11:58:35 Finally AC :), nice problem i had to improve my mu function in nloglogn
	:D: 2012-08-31 06:19:12 The limit is sensible since a lot of users passed it and it's a setters decision to make it strict. And are you sure you had 1946B, not 1,9KB for example? From what I checked it works fine. The only thing I would complain about is that it should be always mentioned in the description. Since 95% of the time there is 50000B, I don't even pay attention to it and it comes out when trying to commit.
	Raghavendran Ramachandran: 2012-08-31 05:13:53 The source limit is too strict. Even a solution of size 1946 bytes was rejected.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-07-30 08:41:46 Finally I got AC. Need a lot of optimizations to solve this problem.