## 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!