PRIC - Prime checker

For this task you will have to check as many numbers as possible to see if they are prime. As not to make the problem I/O oriented, consider the numbers you should check in the following order: first take 1 and then construct the numbers in the sequence after the recursion: ai=(ai-1+1234567890) mod 231. Be careful not to use more than 4096 bytes of code.

Output

For each number you should write to output the digit "1" if the number is prime or the digit "0" if it is not prime.

Score

The score of your program will be the index of the first number in the sequence after which you do not have a correct answer. Because of some limitation you should not write more than 33 333 333 characters to output. If you reach this limit, your score will be adjusted in accordance to your runtime.

Example

Output:
01000000000000000000000000001000010000000001100000

should receive 50 points.


Added by:Gogu
Date:2006-08-29
Time limit:3.5s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-03-19 07:13:54
I got a score of 196786 but i didnt get any points


Last edit: 2017-03-19 10:45:45
2016-07-24 06:36:13
I got score 5,555,555 for Miller-Rabin Primality Test.
2016-07-22 13:02:00
I got score 757,575.
2016-06-03 17:07:54
Ah 27000 in 3s... But if I run for more time it says TLE. Edit: 170000 now

Last edit: 2016-06-03 17:32:53
2016-05-07 17:20:15
If I copy that output line in the example it works, it I copy the output line from my program from my terminal it works, if I submit my program I get a score of 1.... Atleast specify if it is 32 bit architecture or 64.
Already found the problem unsigned long works at home, but I have to use long long here.

Last edit: 2016-05-08 13:45:05
2015-09-12 10:09:30
135000 in C# 2.0 and under 2Kb of code (ID 15115845)

Last edit: 2015-09-12 11:25:55
2015-06-22 11:47:43 Ankush
Did it with Miller-Rabin, only 15650 :/

Last edit: 2015-06-22 11:59:33
2015-03-28 01:34:31 Archit Kapoor
I attempted this problem in Java and got the score of 250000. Now I re-attempted this problem in C and my score is 7000000 something, approx. But my score/points hasn't changed, and so does my rank..!! What should I do..?
Meanwhile, a very good problem; learned a lot..!!

Last edit: 2015-03-28 01:36:59
2015-02-13 19:14:49 Ritesh
@sinha.. meaning even more than 33,333,333, on the basis of the time consumed??
2015-02-13 19:14:49 Ouditchya Sinha
@Ritesh : Please read the last line of "Score" section. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.