can any body inform me the best prime generating algorithm ?

[mohiul alam prince]

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]

Do you know about the Seat of Eratosphean???

[little joey]

Do you know about the Seat of Eratosphean???

Give the man a chair

[anupam]

haha

[medv]

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;

[sohel]

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]

[shamim]

Do you know about the Seat of Eratosphean???

What the devil is an Eratosphean??????

[mohiul alam prince]

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]

[mohiul alam prince]

deleted

[anupam]

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]

[Larry]

There are a few old posts on this..

[osan]

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

[little joey]

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]

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.

[Per]

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

It's not a name, it's a funny spelling error.