SPOJ: TDPRIMES – Printing some primes

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!

Yes No