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

**Moderator:** Board moderators

- 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 ?

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

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

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

### Primes generation algorithm

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;

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

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

[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]for(j=i+i;j<=maxv;j+=i)

prime[j] = false;

[/cpp]

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

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 inpavelph

do u know about Seat of Eratosphean

Do u want to jock with me?

20000000.[/quote]

Last edited by mohiul alam prince on Wed Mar 03, 2004 4:29 pm, edited 2 times in total.

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

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

"Everything should be made simple, but not always simpler"

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

what is Seat of Eratosphean?

please tell me about this:)

please tell me about this:)

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

### thanx joey

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.

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...............?

what next...............?

### Re: thanx joey

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