can any body inform me the best prime generating algorithm ?
Moderator: Board moderators

 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 email 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 email address
prince_ewu@hotmail.com
prince

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

 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.

 Experienced poster
 Posts: 120
 Joined: Sat Nov 01, 2003 6:16 am
 Location: Dhaka (EWU)
here is the method
[/i][/b]
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:)

 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.