can any body inform me the best prime generating algorithm ?

Let's talk about algorithms!

Moderator: Board moderators

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

can any body inform me the best prime generating algorithm ?

Post by mohiul alam prince » Mon Mar 01, 2004 1:58 pm

hi friends

I am trying to solve some prime problems. but maximum time i am getting TLE.Because my algorithm is not good.
can any body help me about this.I want some prime & perfect generating
algorithms

my e-mail address
prince_ewu@hotmail.com

prince

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Mon Mar 01, 2004 2:58 pm

Do you know about the Seat of Eratosphean???

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Mar 01, 2004 6:58 pm

pavelph wrote:Do you know about the Seat of Eratosphean???
Give the man a chair :D

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Mar 01, 2004 8:37 pm

haha :D
"Everything should be made simple, but not always simpler"

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Primes generation algorithm

Post by medv » Wed Mar 03, 2004 12:02 pm

I use this one:

const
MAX = any number you need;

var
primes:array[1..MAX] of boolean;

procedure genprimes;
var
i,j:longint;
begin
FillChar(primes,sizeof(primes),1);
for i:=2 to trunc(sqrt(MAX)) do
if primes[i] then
begin
j:=i*i;
while (j <= MAX) do
begin
primes[j] := False;
j := j + i;
end;
end;
primes[1] := False;
end;

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

similar approach

Post by sohel » Wed Mar 03, 2004 2:54 pm

My approach is similar to yours, except that I do it in c++,

[cpp]
max = max value;
bool prime[max];
fill(prime, max, true);

prime[0] = prime[1] = false;
for(i=2;i<=sqrt(max);i++)
if(prime)
for(j=i+i;j<=maxv;j+=i)
prime[j] = false;
[/cpp]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Mar 03, 2004 3:47 pm

Do you know about the Seat of Eratosphean???
What the devil is an Eratosphean?????? :P

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Mar 03, 2004 4:15 pm

pavelph

do u know about Seat of Eratosphean
Do u want to jock with me?
How many primes are in 20000000.I want to generate in a array.is it possible.If it is possible please inform me.I know 1400000 prime are in
20000000.[/quote]
Last edited by mohiul alam prince on Wed Mar 03, 2004 4:29 pm, edited 2 times in total.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Mar 03, 2004 4:18 pm

deleted

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Mar 05, 2004 5:40 pm

here is the method

Code: Select all

for(i=0;i<N;i++) a[i]=0;a[0]=a[1]=1;
for(i=2;i<N/2;i++)
  if(!a[i])
    for(j=2;i*j<N;j++) a[i*j]=1;
a is a boolean array or int type.
a[i]=0 possitions are prime.
N is the max number to genrate primes.
[/i][/b]
"Everything should be made simple, but not always simpler"

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

Post by Larry » Sat Mar 06, 2004 8:34 am

There are a few old posts on this..

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

?????????

Post by osan » Tue Mar 09, 2004 7:16 pm

what is Seat of Eratosphean?
please tell me about this:)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 10, 2004 1:04 am

There is no Seat of Eratosphean (AFAIK), it's called Sieve of Eratosthenes. Anupams posting describes the method. To expand it to several millions of primes, you would need to compact the booleans into bits. There is some very efficient code for that elsewhere on the board.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

thanx joey

Post by osan » Wed Mar 10, 2004 6:30 pm

thanx joey.
i know about Sieve of Eratosthenes & can do it in bitwise for long range.

but i didn't hear that name Seat of Eratosphean.

anyway if anyone knows better algo than sieve, please tell me about this.
this time WA
what next...............?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Re: thanx joey

Post by Per » Thu Mar 11, 2004 12:41 am

osan wrote:but i didn't hear that name Seat of Eratosphean.
It's not a name, it's a funny spelling error.

Post Reply

Return to “Algorithms”