SPOJ: CPRIME – Prime Number Theorem

Problem Link

http://www.spoj.com/problems/CPRIME/

Problem Description

In this problem,we need to find percentage error for prime number theorem ((pi(x)-lnx)/pi(x)) % where
pi(x) =number of primes not greater than x.

Concepts Used

This problem is based on prime sieve(Sieve of Eratosthenes)..

Code

#include<stdio.h>
#include<vector>
#include<math.h>

/*To check whether a number i is prime or not,we need to check a[i/2] or a[i>>1] whether it is true or false*/
#define isprime(i) (a[i>>1])

/*number is non prime if correpsonding entry is false*/
#define nonprime(i) (a[i>>1]=false)

/*boolean vector used for marking*/
std::vector<bool>a(100000002,true);

/*returns index of largest prime number not greater than key*/
long int binsearch(long long int [],long int low,long int high ,long int key);

/*array used for storing prime numbers*/
static long long int arr[8000000];

int n=100000000;
int i,j,l;

/*stores all the prime numbers less than 10^8 in arr[]*/
void sieve()
{
    for(i=3;i<=10000;i+=2)
    {
        /*we do not need to mark multiples of already marked numbers*/
        while(!isprime(i))
        {
            i+=2;
        }
        j=i*(i-2);
        /*l=(2*i)-implemented using left shift*/
        l=i<<1;
        while((j=j+l)<=n)
            nonprime(j);/*used to set corresponding entry(arr[j>>1]) to false*/
    }
    j=0;
    arr[j]=2;
    for(i=3;i<=n;i+=2)
    {
        if(isprime(i))
        {
            /*if entry corresponding to i is true,i is prime and hence stored in arr[]*/
            arr[++j]=i;
        }
    }
}
int main()
{
    long int n,ans;
    /*stores all the prime numbers in arr[] and j now contains index of the last prime number(0-based indexing)*/
    sieve();

    /*keep scanning the inputs until it is not equal to 0*/
    while(scanf("%ld",&n)==1)
    {
        /*ans stores pi(n) i.e. number of primes not greater than n*/
        if(n==0)
            break;
        if(n>=arr[j])
            ans=j;
        else
            ans=binsearch(arr,0,j,n);
        ans+=1;

        /*calculate percentage error and print*/

        double temp=log(double(n));
        double res=n/temp;
        double res1=ans-res;
        if(res1<0)
        res1=0-res1;
        res=(res1/ans)*100;
        printf("%.1lf\n",res);
    }
    return 0;
}

/*returns index of largest prime number not greater than key*/
long int binsearch(long long int a[],long int low,long int high,long int key)
{
    while(low<(high-1))
    {
        long int m=low+high;
        if(m%2!=0)
            m++;
        int mid=m/2;
        if(a[mid]==key)
            return mid;
        else if(a[high]==key)
            return high;
        else if(key<a[mid])
            high=mid;
        else low=mid;
    }
    return low;
}

Explanation

For a given x,we need to find percentage error for prime number theorem.Since we already have x and we can easily calculate lnx, what remains is pi(x)(number of primes not greater than x).

We can store prime numbers less than 10^8 and then apply binary search on array to find number of primes not greater than x in logn time(if n is size of array which is equal to number of primes less than 10^8) such that it satisfies time complexity requirements.

Please read this post TDKPRIME before reading this post which explains optimal way to store all the prime numbers less than 10^8.

This content has been helpful to you?

Thanks for contributing!

Yes No