GF2  Irreducible polynomials over GF2
Find the number of degree n irreducible polynomials over GF(2). For example: for n=1 there are two such polynoms: x and x+1. For n=2 there is only one: x^{2}+x+1. Note that in R[x] the polynom x^{2} +1 is irreducible, but not over GF(2), because x^{2}+1=(x+1)*(x+1)
Input
A single positive integer n, where n<500000
Output
Output the answer for n.
Example
Input:
201
Output:
15989433276208858463104100421305100522608250813995004946218
Input:
1
Output:
2
Input:
2
Output:
1
Input:
3
Output:
2
hide comments
~!(*(@*!@^&:
20100411 04:09:51
C++ 4.3.2 is faster than 4.0.0.2 

numerix:
20091015 06:59:16
Python isn't too slow for that problem. Multiplication in python IS fast (Karatsuba). The only problem is the output of the large numbers (> 150000 digits), which is veeeery slow in python. So to get AC you have to do some optimizing on that  and use python 2.5 instead of 2.6! Last edit: 20091019 06:02:38 

Lukas Polacek:
20090827 17:27:28
I have learned Haskell for this problem :) If you know Python well you can do this task in Haskell under one hour. 

Robert Gerbicz:
20090531 10:18:16
That means your solution is slow. 

thomas anderson:
20090531 07:33:01
My code is running in 0.01s without print answer, but get TLE when print the output using fputs. How that is possible?


Robert Gerbicz:
20090526 08:33:06
OK, raised the source limit to 4KB. Try to submit your code! 

Robert Gerbicz:
20090526 08:31:50
"why the source limit is so tight?"


~!(*(@*!@^&:
20090526 08:31:50
why the source limit is so tight? 

[Trichromatic] XilinX:
20090526 08:31:50
I've solved this problem in MIPT Online Judge by Ruby, but it seems that Ruby works pretty slow in SPOJ. Last edit: 20090526 02:21:16 
Added by:  Robert Gerbicz 
Date:  20090525 
Time limit:  0.100s0.720s 
Source limit:  4096B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  classic problem, own input 