SPOJ.com - Problem HS08PAUL

HS08PAUL - A conjecture of Paul Erdős

#number-theory

In number theory there is a very deep unsolved conjecture of the Hungarian Paul Erdős (1913-1996), that there exist infinitely many primes of the form x²+1, where x is an integer. However, a weaker form of this conjecture has been proved: there are infinitely many primes of the form x²+y⁴. You don't need to prove this, it is only your task to find the number of (positive) primes not larger than n which are of the form x²+y⁴ (where x and y are integers).

Input

An integer T, denoting the number of testcases (T≤10000). Each of the T following lines contains a positive integer n, where n<10000000.

Output

Output the answer for each n.

Example

Input:
4
1
2
10
9999999

Output:
0
1
2
13175

Submit solution!

hide comments

< Previous 1 2 Next >

	Francky: 2015-02-02 00:30:10 @gerrob or numerix or ?: I didn't solve this problem, but I'm sure it could be nice to set a new task where we are asked to output the sum of E-2-4-primes within a range [a,b] with b-a < m (big a, m not so big). Or something better as you have some keys in hands. But maybe it's a bad idea. If it's a good idea, I'd like you to set such a task. (gerrob) OK, go ahead. Btw, in the past it was a relatively easy hspl problem, my short brute force code here solves the problem in 0.3 seconds. (Francky) Solved ; true it's easy. I'll try to get AC with PY3.4 without precomp (if I can)... Waiting for the next step too ; thanks ;-) Edit : Done(PAUL2) ; Many thanks ; it seems hard. Last edit: 2015-02-03 22:41:13
	numerix: 2015-02-01 22:28:13 @gerrob: Thanks! It's fine, now.
	Robert Gerbicz: 2015-02-01 18:25:14 @numerix: Sorry for my late answer, the problem opened for pypy and included other (new) languages also.
	numerix: 2015-02-01 18:21:58 @gerrob (= problemsetter): After automatic change to Cube cluster, my old Python solution (using psyco) now has the top rank. I appreciate that automatized runtime recalculation without a real rejudge, so that old psyco using AC Python solutions do not change to NZEC/TLE. BUT: As the top rank is not the right place for my solution, I would prefer to submit a fair solution that gets AC within the TL under actual conditions. BUT: My former solution (runtime was 1.14 s on Pyramid and top rank for quite some time) cannot pass without psyco within the new Cube TL. SO: Could you please consider to adjust the TL and/or open it for PyPy? Perhaps PyPy will do without increasing TL. Last edit: 2015-02-01 18:24:36
	Ouditchya Sinha: 2015-02-01 18:21:58 Great problem!!! Loved solving it. :)
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2015-02-01 18:21:58 my compressed precomputation fit on 4096B of source limit ;-) Great Problem, thanks.

Submit solution!

Added by:	Robert Gerbicz
Date:	2009-04-05
Time limit:	1s
Source limit:	4096B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-MONKEY
Resource:	High School Programming League 2008/09