Given a number N. The task is to find the smallest special prime which is greater than or equal to N.
A special prime is a number which can be created by placing digits one after another such the all the resulting numbers are prime.
Examples:
Input: N = 379 Output: 379 379 can be created as => 3 => 37 => 379 Here, all the numbers ie. 3, 37, 379 are prime. Input:N = 100 Output: 233
Approach: The idea is to use Sieve Of Eratosthenes. Build the sieve array up to the number N*10 (Assuming the number will exist in that range). Then start iteratively from the number N checking if the number is prime. If it is prime then check if it is special prime or not.
Now, to check if a number is a special prime or not. Keep dividing the number by 10 and at each point check whether the remaining number is prime or not, which we can do by referring our Sieve array which we have built.
Below is the implementation of the above approach:
C++
// CPP program to find the Smallest Special Prime// which is greater than or equal to a given number#include <bits/stdc++.h>using namespace std;// Function to check whether the number// is a special prime or notbool checkSpecialPrime(bool* sieve, int num){ // While number is not equal to zero while (num) { // If the number is not prime // return false. if (!sieve[num]) { return false; } // Else remove the last digit // by dividing the number by 10. num /= 10; } // If the number has become zero // then the number is special prime, // hence return true return true;}// Function to find the Smallest Special Prime// which is greater than or equal to a given numbervoid findSpecialPrime(int N){ bool sieve[N*10]; // Initially all numbers are considered Primes. memset(sieve, true, sizeof(sieve)); sieve[0] = sieve[1] = false; for (long long i = 2; i <= N*10; i++) { if (sieve[i]) { for (long long j = i * i; j <= N*10; j += i) { sieve[j] = false; } } } // There is always an answer possible while (true) { // Checking if the number is a // special prime or not if (checkSpecialPrime(sieve, N)) { // If yes print the number // and break the loop. cout << N << '\n'; break; } // Else increment the number. else N++; }}// Driver codeint main(){ int N = 379; findSpecialPrime(N); N = 100; findSpecialPrime(N); return 0;} |
Java
// Java program to find the Smallest Special Prime// which is greater than or equal to a given numberclass GFG{ // Function to check whether the number// is a special prime or notstatic boolean checkSpecialPrime(boolean []sieve, int num){ // While number is not equal to zero while (num > 0) { // If the number is not prime // return false. if (sieve[num]) { return false; } // Else remove the last digit // by dividing the number by 10. num /= 10; } // If the number has become zero // then the number is special prime, // hence return true return true;}// Function to find the Smallest Special Prime// which is greater than or equal to a given numberstatic void findSpecialPrime(int N){ boolean[] sieve = new boolean[N * 10 + 1]; // Initially all numbers are considered Primes. sieve[0] = sieve[1] = true; for (int i = 2; i <= N * 10; i++) { if (!sieve[i]) { for (int j = i * i; j <= N * 10; j += i) { sieve[j] = true; } } } // There is always an answer possible while (true) { // Checking if the number is a // special prime or not if (checkSpecialPrime(sieve, N)) { // If yes print the number // and break the loop. System.out.println(N); break; } // Else increment the number. else N++; }}// Driver codepublic static void main(String[] args){ int N = 379; findSpecialPrime(N); N = 100; findSpecialPrime(N);}}// This code contributed by Rajput-Ji |
Python3
# Python 3 program to find the Smallest # Special Prime which is greater than or# equal to a given number# Function to check whether the number# is a special prime or notdef checkSpecialPrime(sieve, num): # While number is not equal to zero while (num): # If the number is not prime # return false. if (sieve[num] == False): return False # Else remove the last digit # by dividing the number by 10. num = int(num / 10) # If the number has become zero # then the number is special prime, # hence return true return True# Function to find the Smallest Special# Prime which is greater than or equal# to a given numberdef findSpecialPrime(N): sieve = [True for i in range(N * 10 + 1)] sieve[0] = False sieve[1] = False # sieve for finding the Primes for i in range(2, N * 10 + 1): if (sieve[i]): for j in range(i * i, N * 10 + 1, i): sieve[j] = False # There is always an answer possible while (True): # Checking if the number is a # special prime or not if (checkSpecialPrime(sieve, N)): # If yes print the number # and break the loop. print(N) break # Else increment the number. else: N += 1# Driver codeif __name__ == '__main__': N = 379 findSpecialPrime(N) N = 100 findSpecialPrime(N)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find the Smallest Special Prime// which is greater than or equal to a given numberusing System;class GFG{ // Function to check whether the number// is a special prime or notstatic bool checkSpecialPrime(bool []sieve, int num){ // While number is not equal to zero while (num > 0) { // If the number is not prime // return false. if (sieve[num]) { return false; } // Else remove the last digit // by dividing the number by 10. num /= 10; } // If the number has become zero // then the number is special prime, // hence return true return true;}// Function to find the Smallest Special Prime// which is greater than or equal to a given numberstatic void findSpecialPrime(int N){ bool[] sieve = new bool[N * 10 + 1]; // Initially all numbers are considered Primes. sieve[0] = sieve[1] = true; for (int i = 2; i <= N * 10; i++) { if (!sieve[i]) { for (int j = i * i; j <= N * 10; j += i) { sieve[j] = true; } } } // There is always an answer possible while (true) { // Checking if the number is a // special prime or not if (checkSpecialPrime(sieve, N)) { // If yes print the number // and break the loop. Console.WriteLine(N); break; } // Else increment the number. else N++; }}// Driver codestatic void Main(){ int N = 379; findSpecialPrime(N); N = 100; findSpecialPrime(N);}}// This code is contributed by mits |
PHP
<?php// PHP program to find the Smallest Special // Prime which is greater than or equal // to a given number // Function to check whether the number // is a special prime or not function checkSpecialPrime($sieve, $num) { // While number is not equal to zero while ($num) { // If the number is not prime // return false. if (!$sieve[$num]) { return false; } // Else remove the last digit // by dividing the number by 10. $num = floor($num / 10); } // If the number has become zero // then the number is special prime, // hence return true return true; } // Function to find the Smallest Special // Prime which is greater than or equal // to a given number function findSpecialPrime($N) { // Initially all numbers are // considered Primes. $sieve = array_fill(0, $N * 10, true); $sieve[0] = $sieve[1] = false; for ($i = 2; $i <= $N * 10; $i++) { if ($sieve[$i]) { for ($j = $i * $i; $j <= $N * 10; $j += $i) { $sieve[$j] = false; } } } // There is always an answer possible while (true) { // Checking if the number is a // special prime or not if (checkSpecialPrime($sieve, $N)) { // If yes print the number // and break the loop. echo $N, "\n"; break; } // Else increment the number. else $N++; } } // Driver code $N = 379; findSpecialPrime($N); $N = 100; findSpecialPrime($N); // This code is contributed by Ryuga?> |
Javascript
<script>// javascript program to find the Smallest Special Prime// which is greater than or equal to a given number // Function to check whether the number// is a special prime or notfunction checkSpecialPrime(sieve , num){ // While number is not equal to zero while (num > 0) { // If the number is not prime // return false. if (sieve[num]) { return false; } // Else remove the last digit // by dividing the number by 10. num = parseInt(num / 10); } // If the number has become zero // then the number is special prime, // hence return true return true;}// Function to find the Smallest Special Prime// which is greater than or equal to a given numberfunction findSpecialPrime(N){ var sieve = Array.from({length: N * 10 + 1}, (_, i) => false); // Initially all numbers are considered Primes. sieve[0] = true; sieve[1] = true; var i = 0, j = 0; for (i = 2; i <= N * 10; i++) { if (!sieve[i]) { for (j = i * i; j <= N * 10; j += i) { sieve[j] = true; } } } // There is always an answer possible while (true) { // Checking if the number is a // special prime or not if (checkSpecialPrime(sieve, N)) { // If yes print the number // and break the loop. document.write(N+"<br>"); break; } // Else increment the number. else N++; }}// Driver codevar N = 379;findSpecialPrime(N);N = 100;findSpecialPrime(N);// This code is contributed by shikhasingrajput </script> |
Output:
379 233
Time Complexity: O(nlog(logn))
Auxiliary Space: O(n)
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!
