Need help on prime numbers

[razibcse]

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 pre-generating???


The time limit of this program is 10 sec...

If someone knows such method, please let me know...

Razib

[Julien Cornebise]

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

[razibcse]

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???

[Julien Cornebise]

Hi
This is not too slow if you don't re-check 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.security-labs.org/index.php3?page=5).
Enjoy !

[rjhadley]

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:

and dividing the number with the primes less than its sqr root...isn't it too slow???

Part of the "science" in computer science is experimenting - you can learn a lot by trying different things...

[razibcse]

thanx guys for your suggestions...
actually I got AC on 10200 already...Just had to pre-calculate 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...

[neo_tohin]

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

[wD]

why don't you post the algorithm here? certain, there's more than one person interested on that
despite saving time in mail replies, the algorithm will be keeped here for later viewing.

Cheers, wD