Need help on prime numbers
Moderator: Board moderators
Need help on prime numbers
Is there any other reliable method of finding whether a number is prime or not than the traditional method?
The system of dividing a number by all the primes less than its square root is too time consuming.
Say, in 10200, when you want to find the number of primes between a certain range. If I precalculate the number,the program works fine, but if I calculate within the program, then it gets TLE always, though in my pc I don't have to wait for the output more than 1 or 2 sec.
I hate to get AC by hard coding..so I wanna know that if there are other methods to find a number's primarility quickly...or this type of problem should always be solved by pregenerating???
The time limit of this program is 10 sec...
If someone knows such method, please let me know...
Razib
The system of dividing a number by all the primes less than its square root is too time consuming.
Say, in 10200, when you want to find the number of primes between a certain range. If I precalculate the number,the program works fine, but if I calculate within the program, then it gets TLE always, though in my pc I don't have to wait for the output more than 1 or 2 sec.
I hate to get AC by hard coding..so I wanna know that if there are other methods to find a number's primarility quickly...or this type of problem should always be solved by pregenerating???
The time limit of this program is 10 sec...
If someone knows such method, please let me know...
Razib
Wisdom is know what to do next; virtue is doing it.

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
How about using erathosten's sieve ?
http://mathworld.wolfram.com/SieveofEratosthenes.html
::EDIT A FEW MOMENT LATER::
Got AC with that method
1974148 2003/10/11 12:17:26.332 Accepted 0:00.523 472 17505 C++ 10200  Prime Time
http://mathworld.wolfram.com/SieveofEratosthenes.html
::EDIT A FEW MOMENT LATER::
Got AC with that method
1974148 2003/10/11 12:17:26.332 Accepted 0:00.523 472 17505 C++ 10200  Prime Time
actually I use the sieve method to generate primes...but in this case,the maximum range is 10000,which yields 10000^2+10000+41,which is really big...how can I test this is prime or not...
and with sieve method, you can generate primes upto 65000..then how do you produce primes???
and dividing the number with the primes less than its sqr root...isn't it too slow???
this is the problem of mine ..what can I do???
and with sieve method, you can generate primes upto 65000..then how do you produce primes???
and dividing the number with the primes less than its sqr root...isn't it too slow???
this is the problem of mine ..what can I do???
Wisdom is know what to do next; virtue is doing it.

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
Hi
This is not too slow if you don't recheck uselessly many times the primality of a number. You can first calc a table of the prime numbers <= sqtr(max number you'll have to check the primality of), and then do the maximum of computations that can be done independently of any test case.
If I tell you more, that would tell you the solution to the problem...
BTW, I think this post could have be sent to the V102 forum.
If you're interested in primality testing, I can tell you that actually, many algorithms are probabilistic : they tell you the probablity that the number is prime, but it's not 100% sure. For example, see the problem about Carmichael Numbers (10006), or the Miller Rabin method (see http://www.securitylabs.org/index.php3?page=5).
Enjoy !
This is not too slow if you don't recheck uselessly many times the primality of a number. You can first calc a table of the prime numbers <= sqtr(max number you'll have to check the primality of), and then do the maximum of computations that can be done independently of any test case.
If I tell you more, that would tell you the solution to the problem...
BTW, I think this post could have be sent to the V102 forum.
If you're interested in primality testing, I can tell you that actually, many algorithms are probabilistic : they tell you the probablity that the number is prime, but it's not 100% sure. For example, see the problem about Carmichael Numbers (10006), or the Miller Rabin method (see http://www.securitylabs.org/index.php3?page=5).
Enjoy !
I agree with Julien that this has now become more of a question about Problem 10200 than a question about primality testing, but for completeness I"ll give you a few (general) suggestions.
1) Note the upper bound is very small for this problem (10 000) and that a solution for any input values can be derived from the information needed to get a solution to the largest possible range.
2) Consider whether it is easier to test if a large number is (a) prime or (b) composite.
4) You ask:
1) Note the upper bound is very small for this problem (10 000) and that a solution for any input values can be derived from the information needed to get a solution to the largest possible range.
2) Consider whether it is easier to test if a large number is (a) prime or (b) composite.
4) You ask:
Part of the "science" in computer science is experimenting  you can learn a lot by trying different things...and dividing the number with the primes less than its sqr root...isn't it too slow???
thanx guys for your suggestions...
actually I got AC on 10200 already...Just had to precalculate the primarility...I knew this approach, but wanted to know about any other faster method that can be implemented in THIS TYPE of problems...
and about probabilistic methods, I solved quite a few problems using those methods...but these problems explicitly say about the corresponding method..such as Carmichael number or farmet's principle...
But I was eager to know whether these probabilistic methods can be applicable to normal prime number problems,where we have to generate primes rather than the conventional Sieve or some other similar method...
Anyway, thanks again for your opinions...
actually I got AC on 10200 already...Just had to precalculate the primarility...I knew this approach, but wanted to know about any other faster method that can be implemented in THIS TYPE of problems...
and about probabilistic methods, I solved quite a few problems using those methods...but these problems explicitly say about the corresponding method..such as Carmichael number or farmet's principle...
But I was eager to know whether these probabilistic methods can be applicable to normal prime number problems,where we have to generate primes rather than the conventional Sieve or some other similar method...
Anyway, thanks again for your opinions...
Wisdom is know what to do next; virtue is doing it.
Nice day isn't it to check prime?
hi there i am a new poster . i think you can see it in left side
i have change the sieve a little.
it generates 1  200000000 primes in just 7 seconds.
wanna know ?
sent mail to me /
i will sent the algroithm .
sorry not the code
i have change the sieve a little.
it generates 1  200000000 primes in just 7 seconds.
wanna know ?
sent mail to me /
i will sent the algroithm .
sorry not the code
Live to die