Need help on prime numbers

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

Need help on prime numbers

Post by razibcse » Sat Oct 11, 2003 11:28 am

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
Wisdom is know what to do next; virtue is doing it.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sat Oct 11, 2003 1:56 pm

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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

Post by razibcse » Sat Oct 11, 2003 9:03 pm

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???
Wisdom is know what to do next; virtue is doing it.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sun Oct 12, 2003 12:06 am

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
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Sun Oct 12, 2003 8:08 pm

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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

Post by razibcse » Sun Oct 12, 2003 9:20 pm

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...
Wisdom is know what to do next; virtue is doing it.

neo_tohin
New poster
Posts: 5
Joined: Wed Dec 31, 2003 11:24 am
Location: Bangladesh
Contact:

Nice day isn't it to check prime?

Post by neo_tohin » Wed Jan 07, 2004 10:03 am

hi there i am a new poster . i think you can see it in left side :P

i have change the sieve a little.
it generates 1 - 200000000 primes in just 7 seconds.

wanna know ? :-?

sent mail to me / :wink:

i will sent the algroithm :wink: .

sorry not the code :evil:
Live to die

User avatar
wD
New poster
Posts: 2
Joined: Mon Dec 22, 2003 12:46 am
Location: Portugal - Aveiro
Contact:

Post by wD » Wed Jan 07, 2004 1:44 pm

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

Cheers, wD
"May God be between you and Evil, in every single path you have to walk"

Post Reply

Return to “Algorithms”