UVA 10200 Prime Time











Hints: Generate numbers from 0 to 10000 by Euler's rule and check every number is prime or not. If prime then mark as prime using array else mark as non prime. Then take input a ,b and by checking array count prime number. Don't forget to consider precision of percentage. Simply add .00000005 with result.




#include <bits/stdc++.h>
using namespace std;
#define n 10050
long long int p[n],k=1,size;
vector<long long int>sg;
bool a[n];
long long int prime()
{
    long long i,j;
    a[0]=a[1]=1;
    for(i=4;i<=n;i=i+2)
    {
        a[i]=1;
    }
    for(i=3;i<=sqrt(n);i=i+2)
    {
        for(j=i*i;j<=n;j=j+2*i)
        {
            a[j]=1;
        }
    }
    p[0]=2;
    for(i=3;i<=n;i=i+2)
    {
        if(a[i]==0)
        {
            p[k]=i;
            //cout<<p[k]<<endl;
            k++;
        }
    }


}

long long int isprime(long long int v)
{
    long long int x;
    if(v<=n)
    {
        if(a[v]==0)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else if(v>n)
    {
    for(x=1;x<=k && p[x]<=sqrt(v);x++)
    {
        if(v%p[x]==0)
        {
            return 0;
        }
    }
    }

    return 1;
}

int main()
{
     long long int m,g,c,r,t,l,h,u,w,i,j,rule,count,d;
     double per,res;
     //freopen("10200in.txt","r",stdin);
     //freopen("10200out.txt","w",stdout);
     prime();


     sg.clear();

        for(i=0;i<=10000;i++)
        {
            rule=i*i+i+41;
            if(isprime(rule))
            {

               sg.push_back(1);

            }
            else
            {
                sg.push_back(0);

            }

        }

        while(cin>>l>>u)
        {
            count=0;
            d=abs(u-l)+1;
            for(i=l;i<=u;i++)
            {

                if(sg[i]==1)
                {
                    count++;
                }

            }

            per=(count*100.0)/(double)d;
            //cout<<per<<endl;

            res=per+.00000005;
            printf("%0.2lf\n",res);

        }

    return 0;
}



Share on Google Plus
Earn @ Wap4dollar.Com

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment