Given two numbers n and k, find whether there exist at least k Special prime numbers or not from 2 to n inclusively.
A prime number is said to be Special prime number if it can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5 + 7 + 1.
Note:- Two prime numbers are called neighboring if there are no other prime numbers between them.
Input : n = 27, k = 2 Output : YES In this sample the answer is YES since at least two numbers are Special 13(5 + 7 + 1) and 19(7 + 11 + 1). Input : n = 45, k = 7 Output : NO In this example, the Special prime numbers are 13(5 + 7 + 1), 19(7 + 11 + 1), 31(13 + 17 + 1), 37(17 + 19 + 1), 43(19 + 23 + 1). As the no. of Special prime numbers from 2 to 45 is less than k, the output is NO.
To solve this problem we need to find prime numbers in range [2..n]. So we us Sieve of Eratosthenes to generate all the prime numbers from 2 to n. Then, Take every pair of neighboring prime numbers and check if their sum increased by 1 is a prime number too. Count the number of these pairs, compare it to K and output the result.
Below is the implementation of the above approach:-
# Python3 program to check whether there
# exist at least k or not in range [2..n]
primes = ;
# Generating all the prime numbers
# from 2 to n.
visited = [False] * (n + 2);
for i in range(2, n + 2):
if (visited[i] == False):
for j in range(i * i, n + 2, i):
visited[j] = True;
def specialPrimeNumbers(n, k):
count = 0;
for i in range(len(primes)):
for j in range(i – 1):
# If a prime number is Special
# prime number, then we increments
# the value of k.
if (primes[j] +
primes[j + 1] + 1 == primes[i]):
count += 1;
# If at least k Special prime numbers
# are present, then we return 1.
# else we return 0 from outside of
# the outer loop.
if (count == k):
# Driver Code
n = 27;
k = 2;
if (specialPrimeNumbers(n, k)):
# This code is contributed by mits