## Problem Link

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

## Problem Description

In this problem,we need to print 1st,101st,201st…….primes less than 10^8.

## Concepts Used

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

## Code

```
#include<stdio.h>
#include<vector>
/*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);
int n=100000000;
int i,j,l;
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*/
}
}
/*print first prime number i.e. 2 */
printf("2\n");
j=0;/*used to keep count of prime numbers*/
/* For all odd numbers(all evens must be non prime) less than 10^8,keep on traversing the bool vector used for marking,and when the count of prime numbers reaches 100,print the prime and reset the count to 0 */
for(i=3;i<=n;i+=2)
{
if(isprime(i))
{
j++;
if(j==100)
{
printf("%d\n",i);
j=0;
}
}
}
}
int main()
{
/*call the function to mark prime numbers in bool vector a[] and print every 100th prime number*/
sieve();
return 0;
}
```

## Explanation

We need to print primes less than `10^8`

(1st,101st,201st…….and so on).So we just need to mark the primes and print them.For explanation on how to mark the primes less than `10^8`

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

.

This content has been helpful to you?

Thanks for contributing!