YCCE02 - Editorial

PROBLEM LINKS

Practice

Contest

Author:SRIKANT BADRI

DIFFICULTY:

SIMPLE

PREREQUISITES:

Concept of Prime

PROBLEM:

To find all prime numbers upto 10^7

EXPLANATION:

To gain 100 points one must know an efficient algorithm to evaluate prime numbers upto 10^7 in 1 sec. One such algorithm is Sieve Of Eratosthenes.

The approach used by this algorithm is:

Step 1:Create a bool arrray having size 10000000.

Step 2:Initialize every value of that array with true & initialize index 0,1 as false since they are not primes.
(You can use memset function in C,C++ for this)

Step 3: Pick a number from bool array which is not false.

Step 4: Make all multiples of that number in the array as false.

Step 5: Repeat step 3 & 4 until all the elements (<=10000000) having true value have not been considered.

Step 6: All the elements having true values are primes.

The code for above algorithm is:


bool Primes[10000003];  
long long int i,j;

	memset(Primes,true,sizeof(Primes));

	Primes[0]=false;

	Primes[1]=false;

	for(i=2;i<=10000000;i++)

	{

		if(Primes[i])

		{

			for(j=i*2;j<=10000000;j+=i)

			{

				Primes[j]=false;

			}

		}

	} 
 

SAMPLE SOLUTION:

Author