Given a big integer,how can i check out whether it's a prime?

[ulyssesmn]

I've tried use a program which is will work in sqrt(n),but it got TLE.,please help me
http://acm.pku.edu.cn/JudgeOnline/problem?id=1811

[vmanes]

If you look back in this forum, the prime number problem has been discussed many, many times in just the past week.

What do you mean by "it got TLE"?

[ulyssesmn]

"TLE" means time limit error,and that integers could be at most 2^54.So with those big numbers cannot be checked out in one second!!!(Even if you've used sqrt(n)!!!)

[vmanes]

"TLE" means time limit error,and that integers could be at most 2^54.So with those big numbers cannot be checked out in one second!!!(Even if you've used sqrt(n)!!!)

I don't think testing a single number of that size presents a time problem. Consider that the square root of 2^54 is 2^27, or about 134 million. On a reasonably modern PC, that is a fairly insignificant task.

Or, are you saying that you have a time limit to meet, and that nothing beyond 2^54 can be done in that time?

The simple, brute force approach we using in teaching examples will, of course, not be the most efficient. There are other algorithms, more complex and mathematically based that you might find and implement.

[ulyssesmn]

Yes, I need very effective algoithm. As you said square root of 2^54 is 2^27(about 134million)
and that will be at least one second,but there would be a lot of numbers to be checked.
So what kind of agorithm shall I use?(or where I can find)

[vmanes]

Yes, I need very effective algoithm. As you said square root of 2^54 is 2^27(about 134million)
and that will be at least one second,but there would be a lot of numbers to be checked.
So what kind of agorithm shall I use?(or where I can find)

Googling for "fast prime number algorithm" will find some references that may be helpful. Here's one