HS08PAUL - A conjecture of Paul Erdős

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 x2+1, where x is an integer. However, a weaker form of this conjecture has been proved: there are infinitely many primes of the form x2+y4. 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 x2+y4 (where x and y are integers).


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 the answer for each n.




hide comments
robosapien: 2020-07-03 19:38:16

100th AC :)
Easy sieve.

rohan121_kumar: 2020-05-29 20:39:31


Last edit: 2020-06-04 09:16:39
shivamvermadev: 2020-04-04 12:27:44

Great Question
Finally Solved it

adist98: 2019-05-05 03:09:04

Last edit: 2019-05-05 03:43:49
Shubham Jadhav: 2017-05-11 17:37:38

Nice Problem. AC in one go :)

Ankit: 2015-08-02 11:14:02

good one:)

[Lakshman]: 2015-02-02 14:07:51

Something strange happend with my code. My last Ac took .20s today I changes my bool arr[] to vector and its Ac in .03s

(Mitch) That's because of template specialisation.

Last edit: 2015-02-02 15:28:49
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.

Added by:Robert Gerbicz
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