Patikrinkite, ar skaičius yra „Palindromic Prime“
A „Palindromic Prime“ (Kartais vadinamas a Palprime ) yra pirminis numeris, kuris taip pat yra palindrominis numeris.
Atsižvelgiant į skaičių n spausdinkite visus palindrominius primas mažesnius ar lygius n. Pavyzdžiui, jei n yra 10, išėjimas turėtų būti 2 3 5 7 '. Ir jei n yra 20, išėjimas turėtų būti 2 3 5 7 11 '.
Idėja yra sugeneruoti visus pirminius skaičius mažesnius arba lygius nurodytam skaičiui N ir tikrinti kiekvieną pirminį skaičių, nesvarbu, ar tai palindrominis, ar ne.
Naudojami metodai
- Sužinoti, ar nurodytas skaičius yra pagrindinis, ar ne- Eratostheneso sieto metodas
- Norėdami patikrinti, ar nurodytas skaičius yra palindrominis skaičius, ar ne: Rekursinė funkcija, skirta tikrinti palindromą
Žemiau yra aukščiau pateikto algoritmo įgyvendinimas:
// C++ Program to print all palindromic primes // smaller than or equal to n. #include using namespace std ; // A function that returns true only if num // contains one digit int oneDigit ( int num ) { // comparison operation is faster than // division operation. So using following // instead of 'return num / 10 == 0;' return ( num >= 0 && num < 10 ); } // A recursive function to find out whether // num is palindrome or not. Initially dupNum // contains address of a copy of num. bool isPalUtil ( int num int * dupNum ) { // Base case (needed for recursion termination): // This statement/ mainly compares the first // digit with the last digit if ( oneDigit ( num )) return ( num == ( * dupNum ) % 10 ); // This is the key line in this method. Note // that all recursive/ calls have a separate // copy of num but they all share same copy // of *dupNum. We divide num while moving up // the recursion tree if ( ! isPalUtil ( num / 10 dupNum )) return false ; // The following statements are executed when // we move up the recursion call tree * dupNum /= 10 ; // At this point if num%10 contains i'th // digit from beginning then (*dupNum)%10 // contains i'th digit from end return ( num % 10 == ( * dupNum ) % 10 ); } // The main function that uses recursive function // isPalUtil() to find out whether num is palindrome // or not int isPal ( int num ) { // If num is negative make it positive if ( num < 0 ) num = - num ; // Create a separate copy of num so that // modifications made to address dupNum don't // change the input number. int * dupNum = new int ( num ); // *dupNum = num return isPalUtil ( num dupNum ); } // Function to generate all primes and checking // whether number is palindromic or not void printPalPrimesLessThanN ( int n ) { // Create a boolean array 'prime[0..n]' and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime else true. bool prime [ n + 1 ]; memset ( prime true sizeof ( prime )); for ( int p = 2 ; p * p <= n ; 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 * 2 ; i <= n ; i += p ) prime [ i ] = false ; } } // Print all palindromic prime numbers for ( int p = 2 ; p <= n ; p ++ ) // checking whether the given number is // prime palindromic or not if ( prime [ p ] && isPal ( p )) cout < < p < < ' ' ; } // Driver Program int main () { int n = 100 ; printf ( 'Palindromic primes smaller than or ' 'equal to %d are : n ' n ); printPalPrimesLessThanN ( n ); }
Java // Java Program to print all palindromic primes // smaller than or equal to n. import java.util.* ; class GFG { // A function that returns true only if num // contains one digit static boolean oneDigit ( int num ) { // comparison operation is faster than // division operation. So using following // instead of 'return num / 10 == 0;' return ( num >= 0 && num < 10 ); } // A recursive function to find out whether // num is palindrome or not. Initially dupNum // contains address of a copy of num. static boolean isPalUtil ( int num int dupNum ) { // Base case (needed for recursion termination): // This statement/ mainly compares the first // digit with the last digit if ( oneDigit ( num )) return ( num == ( dupNum ) % 10 ); // This is the key line in this method. Note // that all recursive/ calls have a separate // copy of num but they all share same copy // of dupNum. We divide num while moving up // the recursion tree if ( ! isPalUtil ( num / 10 dupNum )) return false ; // The following statements are executed when // we move up the recursion call tree dupNum /= 10 ; // At this point if num%10 contains ith // digit from beginning then (dupNum)%10 // contains ith digit from end return ( num % 10 == ( dupNum ) % 10 ); } // The main function that uses recursive function // isPalUtil() to find out whether num is palindrome // or not static boolean isPal ( int num ) { // If num is negative make it positive if ( num < 0 ) num = - num ; // Create a separate copy of num so that // modifications made to address dupNum don't // change the input number. int dupNum = num ; // dupNum = num return isPalUtil ( num dupNum ); } // Function to generate all primes and checking // whether number is palindromic or not static void printPalPrimesLessThanN ( int n ) { // Create a boolean array 'prime[0..n]' and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime else true. boolean prime [] = new boolean [ n + 1 ] ; Arrays . fill ( prime true ); for ( int p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed then it is // a prime if ( prime [ p ] ) { // Update all multiples of p for ( int i = p * 2 ; i <= n ; i += p ){ prime [ i ] = false ;} } } // Print all palindromic prime numbers for ( int p = 2 ; p <= n ; p ++ ){ // checking whether the given number is // prime palindromic or not if ( prime [ p ] && isPal ( p )){ System . out . print ( p + ' ' ); } } } // Driver function public static void main ( String [] args ) { int n = 100 ; System . out . printf ( 'Palindromic primes smaller than or ' + 'equal to %d are :n' n ); printPalPrimesLessThanN ( n ); } } // This code is contributed by Arnav Kr. Mandal.
Python # Python3 Program to print all palindromic # primes smaller than or equal to n. # A function that returns true only if # num contains one digit def oneDigit ( num ): # comparison operation is faster than # division operation. So using following # instead of 'return num / 10 == 0;' return ( num >= 0 and num < 10 ); # A recursive function to find out whether # num is palindrome or not. Initially dupNum # contains address of a copy of num. def isPalUtil ( num dupNum ): # Base case (needed for recursion termination): # This statement/ mainly compares the first # digit with the last digit if ( oneDigit ( num )): return ( num == ( dupNum ) % 10 ); # This is the key line in this method. Note # that all recursive/ calls have a separate # copy of num but they all share same copy # of dupNum. We divide num while moving up # the recursion tree if ( not isPalUtil ( int ( num / 10 ) dupNum )): return False ; # The following statements are executed # when we move up the recursion call tree dupNum = int ( dupNum / 10 ); # At this point if num%10 contains ith # digit from beginning then (dupNum)%10 # contains ith digit from end return ( num % 10 == ( dupNum ) % 10 ); # The main function that uses recursive # function isPalUtil() to find out whether # num is palindrome or not def isPal ( num ): # If num is negative make it positive if ( num < 0 ): num = - num ; # Create a separate copy of num so that # modifications made to address dupNum # don't change the input number. dupNum = num ; # dupNum = num return isPalUtil ( num dupNum ); # Function to generate all primes and checking # whether number is palindromic or not def printPalPrimesLessThanN ( n ): # Create a boolean array 'prime[0..n]' and # initialize all entries it as true. A value # in prime[i] will finally be false if i is # Not a prime else true. prime = [ True ] * ( n + 1 ); p = 2 ; while ( p * p <= n ): # If prime[p] is not changed # then it is a prime if ( prime [ p ]): # Update all multiples of p for i in range ( p * 2 n + 1 p ): prime [ i ] = False ; p += 1 ; # Print all palindromic prime numbers for p in range ( 2 n + 1 ): # checking whether the given number # is prime palindromic or not if ( prime [ p ] and isPal ( p )): print ( p end = ' ' ); # Driver Code n = 100 ; print ( 'Palindromic primes smaller' 'than or equal to' n 'are :' ); printPalPrimesLessThanN ( n ); # This code is contributed by chandan_jnu
C# // C# Program to print all palindromic // primes smaller than or equal to n. using System ; class GFG { // A function that returns true only // if num contains one digit static bool oneDigit ( int num ) { // comparison operation is faster than // division operation. So using following // instead of 'return num / 10 == 0;' return ( num >= 0 && num < 10 ); } // A recursive function to find out whether // num is palindrome or not. Initially dupNum // contains address of a copy of num. static bool isPalUtil ( int num int dupNum ) { // Base case (needed for recursion termination): // This statement/ mainly compares the first // digit with the last digit if ( oneDigit ( num )) return ( num == ( dupNum ) % 10 ); // This is the key line in this method. Note // that all recursive/ calls have a separate // copy of num but they all share same copy // of dupNum. We divide num while moving up // the recursion tree if ( ! isPalUtil ( num / 10 dupNum )) return false ; // The following statements are executed when // we move up the recursion call tree dupNum /= 10 ; // At this point if num%10 contains ith // digit from beginning then (dupNum)%10 // contains ith digit from end return ( num % 10 == ( dupNum ) % 10 ); } // The main function that uses recursive // function isPalUtil() to find out // whether num is palindrome or not static bool isPal ( int num ) { // If num is negative make it positive if ( num < 0 ) num = - num ; // Create a separate copy of num so that // modifications made to address dupNum don't // change the input number. int dupNum = num ; // dupNum = num return isPalUtil ( num dupNum ); } // Function to generate all primes and checking // whether number is palindromic or not static void printPalPrimesLessThanN ( int n ) { // Create a boolean array 'prime[0..n]' and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime else true. bool [] prime = new bool [ n + 1 ]; for ( int i = 0 ; i < n + 1 ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed // then it is a prime if ( prime [ p ]) { // Update all multiples of p for ( int i = p * 2 ; i <= n ; i += p ){ prime [ i ] = false ;} } } // Print all palindromic prime numbers for ( int p = 2 ; p <= n ; p ++ ){ // checking whether the given number is // prime palindromic or not if ( prime [ p ] && isPal ( p )){ Console . Write ( p + ' ' ); } } } // Driver function public static void Main () { int n = 100 ; Console . Write ( 'Palindromic primes smaller than or ' + 'equal to are :n' n ); printPalPrimesLessThanN ( n ); } } // This code is contributed by nitin mittal.
JavaScript // javascript Program to print all palindromic primes // smaller than or equal to n. // A function that returns true only if num // contains one digit function oneDigit ( num ) { // comparison operation is faster than // division operation. So using following // instead of 'return num / 10 == 0;' return ( num >= 0 && num < 10 ); } // A recursive function to find out whether // num is palindrome or not. Initially dupNum // contains address of a copy of num. function isPalUtil ( num dupNum ) { // Base case (needed for recursion termination): // This statement/ mainly compares the first // digit with the last digit if ( oneDigit ( num )) return ( num == ( dupNum ) % 10 ); // This is the key line in this method. Note // that all recursive/ calls have a separate // copy of num but they all share same copy // of dupNum. We divide num while moving up // the recursion tree if ( ! isPalUtil ( parseInt ( num / 10 ) dupNum )) return false ; // The following statements are executed when // we move up the recursion call tree dupNum = parseInt ( dupNum / 10 ); // At this point if num%10 contains ith // digit from beginning then (dupNum)%10 // contains ith digit from end return ( num % 10 == ( dupNum ) % 10 ); } // The main function that uses recursive function // isPalUtil() to find out whether num is palindrome // or not function isPal ( num ) { // If num is negative make it positive if ( num < 0 ) num = - num ; // Create a separate copy of num so that // modifications made to address dupNum don't // change the input number. var dupNum = num ; // dupNum = num return isPalUtil ( num dupNum ); } // Function to generate all primes and checking // whether number is palindromic or not function printPalPrimesLessThanN ( n ) { // Create a boolean array 'prime[0..n]' and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime else true. var prime = Array . from ({ length : n + 1 } ( _ i ) => true ); for ( p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed then it is // a prime if ( prime [ p ]) { // Update all multiples of p for ( i = p * 2 ; i <= n ; i += p ) { prime [ i ] = false ; } } } // Print all palindromic prime numbers for ( p = 2 ; p <= n ; p ++ ) { // checking whether the given number is // prime palindromic or not if ( prime [ p ] && isPal ( p )) { console . log ( p ); } } } // Driver function var n = 100 ; console . log ( 'Palindromic primes smaller than or equal to ' + n + ' are :' ); printPalPrimesLessThanN ( n );
PHP // PHP Program to print all palindromic // primes smaller than or equal to n. // A function that returns true only // if num contains one digit function oneDigit ( $num ) { // comparison operation is faster than // division operation. So using following // instead of 'return num / 10 == 0;' return ( $num >= 0 && $num < 10 ); } // A recursive function to find out whether // num is palindrome or not. Initially // dupNum contains address of a copy of num. function isPalUtil ( $num $dupNum ) { // Base case (needed for recursion termination): // This statement/ mainly compares the first // digit with the last digit if ( oneDigit ( $num )) return ( $num == ( $dupNum ) % 10 ); // This is the key line in this method. Note // that all recursive/ calls have a separate // copy of num but they all share same copy // of dupNum. We divide num while moving up // the recursion tree if ( ! isPalUtil (( int )( $num / 10 ) $dupNum )) return false ; // The following statements are executed // when we move up the recursion call tree $dupNum = ( int )( $dupNum / 10 ); // At this point if num%10 contains ith // digit from beginning then (dupNum)%10 // contains ith digit from end return ( $num % 10 == ( $dupNum ) % 10 ); } // The main function that uses recursive // function isPalUtil() to find out whether // num is palindrome or not function isPal ( $num ) { // If num is negative make it positive if ( $num < 0 ) $num = - $num ; // Create a separate copy of num so that // modifications made to address dupNum // don't change the input number. $dupNum = $num ; // dupNum = num return isPalUtil ( $num $dupNum ); } // Function to generate all primes and checking // whether number is palindromic or not function printPalPrimesLessThanN ( $n ) { // Create a boolean array 'prime[0..n]' and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime else true. $prime = array_fill ( 0 $n + 1 true ); for ( $p = 2 ; $p * $p <= $n ; $p ++ ) { // If prime[p] is not changed then // it is a prime if ( $prime [ $p ]) { // Update all multiples of p for ( $i = $p * 2 ; $i <= $n ; $i += $p ) { $prime [ $i ] = false ; } } } // Print all palindromic prime numbers for ( $p = 2 ; $p <= $n ; $p ++ ) { // checking whether the given number // is prime palindromic or not if ( $prime [ $p ] && isPal ( $p )) { print ( $p . ' ' ); } } } // Driver Code $n = 100 ; print ( 'Palindromic primes smaller ' . 'than or equal to ' . $n . ' are : n ' ); printPalPrimesLessThanN ( $n ); // This code is contributed by mits ?>
Išvestis:
Palindromic primes smaller than or equal to 100 are :
2 3 5 7 11
