HXPRIM - Editorial

PROBLEM LINK:

Practice

Contest

Author: rahul_ojha_07

Tester: rahul_ojha_07

DIFFICULTY:

EASY

PREREQUISITES:

Prime Numbers, Sieve of Eratosthenes

PROBLEM:

Find the number of Prime number within a Range N That when added 6 to it also gives a Prime Number.

EXPLANATION:

The problem is to find the number of Prime number within a range N which gives a prime number when added 6 to it.
For solving the problem we can create an Array of prime numbers using Sieve of Eratosthenes.

for(int p=2;p*p ≤ n;p+=1)
{
    if(prime[p]==true)
    {
        for(int i=p*p;i ≤ n;i+=p)
        {
            prime[i]=false;
        }
    }
}

Then for checking if a prime number gives a prime number on adding 6 . we need to initialize a counter variable Count = 0 and iterating over the array using a loop and for each loop checking if a number of prime at certain index i then the index i+6 should also be a prime number if this is the case we can increase the Count by one iterating over the array for N times we can count the number of Hex Prime.
The Implementation for the above statement is given below.

int c=0;
for(int p=2;p ≤ N;p+=1)
{
  if(prime[p]==true and prime[p+6]==true)
    c+=1;
}

To know more about this property of Prime number click here

Author’s solution can be found here.

1 Like