Page **1** of **2**

### can any body inform me the best prime generating algorithm ?

Posted: **Mon Mar 01, 2004 1:58 pm**

by **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

Posted: **Mon Mar 01, 2004 2:58 pm**

by **pavelph**

Do you know about the Seat of Eratosphean???

Posted: **Mon Mar 01, 2004 6:58 pm**

by **little joey**

pavelph wrote:Do you know about the Seat of Eratosphean???

Give the man a chair

Posted: **Mon Mar 01, 2004 8:37 pm**

by **anupam**

haha

### Primes generation algorithm

Posted: **Wed Mar 03, 2004 12:02 pm**

by **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;

### similar approach

Posted: **Wed Mar 03, 2004 2:54 pm**

by **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]

Posted: **Wed Mar 03, 2004 3:47 pm**

by **shamim**

Do you know about the Seat of Eratosphean???

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

Posted: **Wed Mar 03, 2004 4:15 pm**

by **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]

Posted: **Wed Mar 03, 2004 4:18 pm**

by **mohiul alam prince**

deleted

Posted: **Fri Mar 05, 2004 5:40 pm**

by **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]

Posted: **Sat Mar 06, 2004 8:34 am**

by **Larry**

There are a few old posts on this..

### ?????????

Posted: **Tue Mar 09, 2004 7:16 pm**

by **osan**

what is Seat of Eratosphean?

please tell me about this:)

Posted: **Wed Mar 10, 2004 1:04 am**

by **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.

### thanx joey

Posted: **Wed Mar 10, 2004 6:30 pm**

by **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.

### Re: thanx joey

Posted: **Thu Mar 11, 2004 12:41 am**

by **Per**

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

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