Given a number N, the task is to print the Kth prime number greater than N.
Note: N and K are so given that answers are always less than 10^6.
Examples:
Input: N = 5, K = 5
Output: 19
Input: N = 10, K = 3
Output: 17
A simple solution for this problem is to iterate from n+1 to 10^6 and for every number, check if it is prime and print the Kth prime number. This solution looks fine if there is only one query. But not efficient if there are multiple queries.
An efficient solution for this problem is to generate all primes less than 10^6 using Sieve of Eratosthenes and iterate from n+1 to 10^6 and then print the Kth prime number.
C++
// CPP program to print the Kth prime greater than N#include <bits/stdc++.h>using namespace std;// set the MAX_SIZE of the array to 10^6const int MAX_SIZE = 1e6;// initialize the prime arraybool prime[MAX_SIZE + 1];void sieve(){ // set all numbers as prime for time being memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= MAX_SIZE; p++) { // if prime[p] is not changed, then it is a prime if (prime[p] == true) { // update all multiples of p for (int i = p * p; i <= MAX_SIZE; i += p) prime[i] = false; } }}// Function to find the kth prime greater than nint kthPrimeGreaterThanN(int n, int k){ int res = -1; // looping through the numbers greater than n for (int i = n + 1; i < MAX_SIZE; i++) { // decrement k if i is prime if (prime[i] == true) k--; // store the kth prime greater than n if (k == 0) { res = i; break; } } return res;}// Driver codeint main(){ sieve(); int n = 2, k = 15; // Print the kth prime number greater than n cout << kthPrimeGreaterThanN(n, k); return 0;} |
Java
// Java program to print the // Kth prime greater than Nimport java.util.*;class GFG {// set the MAX_SIZE of the array to 10^6static int MAX_SIZE = (int) 1e6;// initialize the prime arraystatic boolean []prime = new boolean[MAX_SIZE + 1];static void sieve(){ // set all numbers as prime for time being Arrays.fill(prime, true); for (int p = 2; p * p <= MAX_SIZE; p++) { // if prime[p] is not changed, // then it is a prime if (prime[p] == true) { // update all multiples of p for (int i = p * p; i <= MAX_SIZE; i += p) prime[i] = false; } }}// Function to find the kth prime greater than nstatic int kthPrimeGreaterThanN(int n, int k){ int res = -1; // looping through the numbers greater than n for (int i = n + 1; i < MAX_SIZE; i++) { // decrement k if i is prime if (prime[i] == true) k--; // store the kth prime greater than n if (k == 0) { res = i; break; } } return res;}// Driver codepublic static void main(String[] args){ sieve(); int n = 2, k = 15; // Print the kth prime number greater than n System.out.println(kthPrimeGreaterThanN(n, k));}} // This code is contributed by 29AjayKumar |
Python 3
# Python 3 program to print the Kth# prime greater than N # set the MAX_SIZE of the array to 10^6MAX_SIZE = int(1e6)# initialize the prime arrayprime = [True] * (MAX_SIZE + 1)# Code for Sieve of Eratosthenesdef sieve(): p = 2 while (p * p <= MAX_SIZE): # if prime[p] is not changed, # then it is a prime if (prime[p] == True): # update all multiples of p for i in range(p * p, MAX_SIZE, p): prime[i] = False p += 1# Function to find the kth prime# greater than n def kthPrimeGreaterThanN(n, k): res = -1 # looping through the numbers # greater than n for i in range(n + 1, MAX_SIZE): # decrement k if i is prime if (prime[i] == True): k -= 1 # store the kth prime greater than n if (k == 0): res = i break return res# Driver Codeif __name__=='__main__': n = 2 k = 15 sieve() # Print the kth prime number # greater than n print(kthPrimeGreaterThanN(n, k)) # This code is contributed by Rupesh Rao |
C#
// C# program to print the // Kth prime greater than Nusing System;using System.Collections.Generic; class GFG {// set the MAX_SIZE of the array to 10^6static int MAX_SIZE = (int) 1e6;// initialize the prime arraystatic Boolean []prime = new Boolean[MAX_SIZE + 1];static void sieve(){ // set all numbers as prime for time being for (int i = 0; i < MAX_SIZE + 1; i++) prime[i] = true; for (int p = 2; p * p <= MAX_SIZE; p++) { // if prime[p] is not changed, // then it is a prime if (prime[p] == true) { // update all multiples of p for (int i = p * p; i <= MAX_SIZE; i += p) prime[i] = false; } }}// Function to find the kth prime greater than nstatic int kthPrimeGreaterThanN(int n, int k){ int res = -1; // looping through the numbers greater than n for (int i = n + 1; i < MAX_SIZE; i++) { // decrement k if i is prime if (prime[i] == true) k--; // store the kth prime greater than n if (k == 0) { res = i; break; } } return res;}// Driver codepublic static void Main(String[] args){ sieve(); int n = 2, k = 15; // Print the kth prime number greater than n Console.WriteLine(kthPrimeGreaterThanN(n, k));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to print // the Kth prime greater than N// set the MAX_SIZE of the array to 10^6var MAX_SIZE = 1000006;// initialize the prime arrayvar prime = Array(MAX_SIZE + 1).fill(true);function sieve(){ for (var p = 2; p * p <= MAX_SIZE; p++) { // if prime[p] is not changed, then it is a prime if (prime[p] == true) { // update all multiples of p for (var i = p * p; i <= MAX_SIZE; i += p) prime[i] = false; } }}// Function to find the kth prime greater than nfunction kthPrimeGreaterThanN(n, k){ var res = -1; // looping through the numbers greater than n for (var i = n + 1; i < MAX_SIZE; i++) { // decrement k if i is prime if (prime[i] == true) k--; // store the kth prime greater than n if (k == 0) { res = i; break; } } return res;}// Driver codesieve();var n = 2, k = 15;// Print the kth prime number greater than ndocument.write( kthPrimeGreaterThanN(n, k));</script> |
Output
53
Naive Approach:
Approach:
In this approach, we will check each number greater than N whether it is a prime number or not. We will keep a counter variable to count the number of prime numbers found. Once the counter reaches K, we will return the last prime number found
Step 1: Define a function is_prime that takes a number as input and returns True if it is a prime number, False otherwise.
Step 2: Define a function kth_prime_naive that takes two inputs, N and K, and returns the Kth prime number greater than N using a naive approach.
Step 3: Initialize a count variable to 0.
Step 4: Loop through all numbers from N+1 to N+K^2.
Step 5: Check whether each number is a prime number using the is_prime function. If it is, increment the count variable.
Step 6: If the count variable is equal to K, return the current number.
Step 7: If the loop completes without finding K prime numbers, return None.
C++
#include <iostream>#include <cmath> using namespace std;// Function to check if a number is primebool isPrime(int num) { if (num < 2) { return false; // Numbers less than 2 are not prime } for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0) { return false; // If divisible by any number between 2 and sqrt(num), it's not prime } } return true; // If not divisible by any numbers, it's prime}// Function to find the Kth prime number starting from N+1int kthPrimeNaive(int N, int K) { int count = 0; // Counter to keep track of the found prime numbers for (int i = N + 1; ; i++) { if (isPrime(i)) { count++; if (count == K) { return i; // Return the Kth prime number } } }}//Driver Codeint main() { cout << kthPrimeNaive(5, 5) << endl; // Output: 19 (5th prime number starting from 6) cout << kthPrimeNaive(10, 3) << endl; // Output: 17 (3rd prime number starting from 11) return 0;} |
Python3
def is_prime(num): if num < 2: return False for i in range(2, int(num**0.5) + 1): if num % i == 0: return False return Truedef kth_prime_naive(N, K): count = 0 for i in range(N + 1, N + K**2): if is_prime(i): count += 1 if count == K: return i return None# Example usage:print(kth_prime_naive(5, 5)) # Output: 19print(kth_prime_naive(10, 3)) # Output: 17 |
C#
using System;class Program{ // Function to check if a number is prime static bool IsPrime(int num) { if (num < 2) { return false; // Numbers less than 2 are not prime } for (int i = 2; i <= Math.Sqrt(num); i++) { if (num % i == 0) { return false; // If divisible by any number between 2 and sqrt(num), it's not prime } } return true; // If not divisible by any numbers, it's prime } // Function to find the Kth prime number starting from N+1 static int KthPrimeNaive(int N, int K) { int count = 0; // Counter to keep track of the found prime numbers for (int i = N + 1; ; i++) { if (IsPrime(i)) { count++; if (count == K) { return i; // Return the Kth prime number } } } } // Driver Code static void Main() { Console.WriteLine(KthPrimeNaive(5, 5)); // Output: 19 (5th prime number starting from 6) Console.WriteLine(KthPrimeNaive(10, 3)); // Output: 17 (3rd prime number starting from 11) }} |
Javascript
function isPrime(num) { if (num < 2) { return false; } for (let i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) { return false; } } return true;}function kthPrimeNaive(N, K) { let count = 0; for (let i = N + 1; count < K * K; i++) { if (isPrime(i)) { count++; if (count === K) { return i; } } } return null;}// Example usage:console.log(kthPrimeNaive(5, 5)); // Output: 19console.log(kthPrimeNaive(10, 3)); // Output: 17 |
Output
19 17
Time Complexity: O(N*K)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
