Life of student

All about Programming , C++ ,Fedora

solve prime1 problem in spoj and codechef

Posted by pankaj4u4m on August 27, 2009

If you will search in net by giving the name “prime1″ you will see so many code which successfully solve this problem.Here is my submission for this problem in codechef
void prime(int L,int U) {
int d=U-L+1;
bool flag[d];
memset(flag,true,sizeof (flag));//all true
for (int i=L%2;i<d;i+=2){ flag[i]=false;}//every position of even number false
for (int i=3;i<d;i+=2)
{
//if (flag[i]==true) continue;//given number is already set prime
int mod=L%i;
int t;
if(mod>0)t=i-mod;
else t=mod;
if(L/i==1||L/i==0)t+=i;
for(int j=t;j<d;j+=i){flag[j]=false;}
}

if (L<=1) flag[1-L]=false;
if (L<=2) {printf("2\n");}
for (int i=L%2?0:1;i<d;i+=2) if (flag[i]==true) printf("%d\n",L+i);

}
this function take the two number and print all the prime number betweem them.
EXPLANATION:
1.first set bol as true assuming that all number can be prime.
2.then set false for those which is divided by 2.
3.Now run for loop for all odd number and check if it is a prime if not proceed for next number else proceed for steps in for loop.
4.inside for loop leave first number because it is prime number and them set all other number which will divide by this prime number.
5.At last print all the prime number.:)

REFERENCES:
1.Sieve_of_Eratosthenes

About these ads

One Response to “solve prime1 problem in spoj and codechef”

  1. Nirmal Kumar said

    Thanks a lot , the tutorial is nice

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: