Investigating the primality of numbers of the form 2n^2-1
It is not so easy to find an efficient algorithm. I checked the discussion, a lot of people' code runs for several minutes to several hours. (If my code cannot finish in 15 minutes, I will definitely kill it). But still more than 2100 people solved it. It is really strange.
I checked my old code, it looks like that I googled out something from the Internet to solve this problem. Otherwise I have no idea how to solve it.
This time, I am equipped with a weapon that is related to quadratic residue. My first implementation needs 8 second. Then I checked the discussion, I found stubbscroll has a better solution. I used some of his idea, the run time is reduced to 5 seconds. I also run his code, it only takes 4 seconds. That is probably due to my powmod function.
No comments:
Post a Comment