Segmented Sieve

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:

Segmented Sieve

Post by razibcse » Sun Oct 26, 2003 8:48 pm

I found that segmented sieve can be used to find large primes and it's more time & space efficient than the conventional one...but I didn't find any implementation or explanation...can somebody explain this method to me please...

Razib :roll:
Wisdom is know what to do next; virtue is doing it.

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid » Sun Oct 26, 2003 10:04 pm

Sieve is efficient, but for soo much prime numbers generation. it may exceeded memory limit, isnt it?

so, what will I do for generate primes for very very large numbers ?
Sajid Online: www.sajidonline.com

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 26, 2003 10:26 pm

Use a randomized algorithm.

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid » Sun Oct 26, 2003 10:28 pm

What is the Randomized algorithm? Plz, eXplain.
Sajid Online: www.sajidonline.com

User avatar
Russell John
New poster
Posts: 40
Joined: Mon Jul 21, 2003 9:21 am
Location: Planet Earth
Contact:

Post by Russell John » Thu Oct 30, 2003 3:06 pm

Sajid wrote:What is the Randomized algorithm? Plz, eXplain.
Randomized algorithm: any algorithm that makes some random (or pseudorandom) choices.
1024 Programmer's Lane,
Algorithm City, United States of C++,
Planet Earth.

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid » Thu Oct 30, 2003 3:14 pm

Russell, Thanx , but still its not clear to me.
Can you give any eXample?
Sajid Online: www.sajidonline.com

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Thu Oct 30, 2003 7:07 pm

Check out for example, the Rabin test, or Lehmer's primality test (use google)

Post Reply

Return to “Algorithms”