problem 1 sieve method

 problem 1 sieve method 

//problem 1(sieve method)

#include<stdio.h>

int isprime[1005];//0 means prime

void sieve()

{

    isprime[0]=1;

    isprime[1]=1;// 0 and 1 are not prime so already marked

    for(int i=2;i*i<=1000;i++)

    {

        if(isprime[i]==0)

        {

            for(int j=i*i;j<=1000;j+=i)

            {

                isprime[j]=1;//marked multiple of i

            }

        }

    }

}

int main()

{

     sieve();

      while(1)

      {

          int n;

          scanf("%d",&n);

          if(isprime[n]==0)printf("Prime\n");

          else printf("Not prime\n");

      }

    return 0;

}