Сфенично число
Опитайте в GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } А Сфенично число е положително цяло число п което е произведение на точно три различни прости числа. Първите няколко сфенични числа са 30 42 66 70 78 102 105 110 114 ...
Дадено е число п определи дали е сфенично число или не.
Примери:
Препоръчителна практика Сфенично число Опитайте!Вход : 30
Изход : Да
Обяснение : 30 е най-малкото сфенично число
30 = 2 × 3 × 5 произведението на най-малките три прости числаВход : 60
Изход : Не
Обяснение : 60 = 2 2 x 3 x 5 има точно 3 прости множители, но не е сфеническо число
Сфеничното число може да се провери от факта, че всяко сфенично число ще има точно 8 делителя СФЕНИЧНО ЧИСЛО
Така че първо ще се опитаме да намерим дали числото има точно 8 делителя, ако не, тогава простият отговор е не. Ако има точно 8 делителя, тогава ще потвърдим дали първите 3 цифри след 1 са прости или не.
напр. 30 (сфенично число)
30=p*q*r(т.е. pq и r са три различни прости номера и техният продукт е 30)
множеството от делител е (12356101530).
По-долу е изпълнението на идеята.
C++ // C++ program to check whether a number is a // Sphenic number or not #include using namespace std ; //create a global array of size 10001; bool arr [ 1001 ]; // This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. void simpleSieve () { // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime else true. memset ( arr true sizeof ( arr )); // One by one traverse all numbers so that their // multiples can be marked as composite. for ( int p = 2 ; p * p < 1001 ; p ++ ) { // If p is not changed then it is a prime if ( arr [ p ]) { // Update all multiples of p for ( int i = p * 2 ; i < 1001 ; i = i + p ) arr [ i ] = false ; } } } int find_sphene ( int N ) { int arr1 [ 8 ] = { 0 }; //to store the 8 divisors int count = 0 ; //to count the number of divisor int j = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( N % i == 0 && count < 9 ) { count ++ ; arr1 [ j ++ ] = i ; } } //finally check if there re 8 divisor and all the numbers are distinct prime no return 1 //else return 0 if ( count == 8 && ( arr [ arr1 [ 1 ]] && arr [ arr1 [ 2 ]] && arr [ arr1 [ 3 ]])) return 1 ; return 0 ; } // Driver program to test above function int main () { int n = 60 ; simpleSieve (); int ans = find_sphene ( n ); if ( ans ) cout < < 'Yes' ; else cout < < 'NO' ; }
Java // Java program to check whether a number is a // Sphenic number or not import java.util.* ; class GFG { // create a global array of size 10001; static boolean [] arr = new boolean [ 1001 ] ; // This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. static void simpleSieve () { // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime else true. Arrays . fill ( arr true ); // One by one traverse all numbers so that their // multiples can be marked as composite. for ( int p = 2 ; p * p < 1001 ; p ++ ) { // If p is not changed then it is a prime if ( arr [ p ] ) { // Update all multiples of p for ( int i = p * 2 ; i < 1001 ; i = i + p ) arr [ i ] = false ; } } } static int find_sphene ( int N ) { int [] arr1 = new int [ 8 ] ; // to store the 8 divisors int count = 0 ; // to count the number of divisor int j = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( N % i == 0 && count < 8 ) { count ++ ; arr1 [ j ++] = i ; } } // finally check if there re 8 divisor and // all the numbers are distinct prime no return 1 // else return 0); if ( count == 8 && ( arr [ arr1 [ 1 ]] && arr [ arr1 [ 2 ]] && arr [ arr1 [ 3 ]] )) return 1 ; return 0 ; } // Driver code public static void main ( String [] args ) { int n = 60 ; simpleSieve (); int ans = find_sphene ( n ); if ( ans == 1 ) System . out . print ( 'Yes' ); else System . out . print ( 'NO' ); } } // This code is contributed by aashish1995
C# // C# program to check whether a number // is a Sphenic number or not using System ; class GFG { // Create a global array of size 10001; static bool [] arr = new bool [ 1001 ]; // This functions finds all primes smaller than // 'limit'. Using simple sieve of eratosthenes. static void simpleSieve () { // Initialize all entries of it as true. // A value in mark[p] will finally be // false if 'p' is Not a prime else true. for ( int i = 0 ; i < 1001 ; i ++ ) arr [ i ] = true ; // One by one traverse all numbers so // that their multiples can be marked // as composite. for ( int p = 2 ; p * p < 1001 ; p ++ ) { // If p is not changed then it // is a prime if ( arr [ p ]) { // Update all multiples of p for ( int i = p * 2 ; i < 1001 ; i = i + p ) arr [ i ] = false ; } } } static int find_sphene ( int N ) { // To store the 8 divisors int [] arr1 = new int [ 8 ]; // To count the number of divisor int count = 0 ; int j = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( N % i == 0 && count < 8 ) { count ++ ; arr1 [ j ++ ] = i ; } } // Finally check if there re 8 divisor // and all the numbers are distinct prime // no return 1 else return 0); if ( count == 8 && ( arr [ arr1 [ 1 ]] && arr [ arr1 [ 2 ]] && arr [ arr1 [ 3 ]])) return 1 ; return 0 ; } // Driver code public static void Main ( String [] args ) { int n = 60 ; simpleSieve (); int ans = find_sphene ( n ); if ( ans == 1 ) Console . Write ( 'Yes' ); else Console . Write ( 'NO' ); } } // This code is contributed by aashish1995
JavaScript < script > // javascript program to check whether a number is a // Sphenic number or not // create a global array of size 10001; // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime else true. let arr = Array ( 1001 ). fill ( true ); // This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. function simpleSieve () { // One by one traverse all numbers so that their // multiples can be marked as composite. for ( let p = 2 ; p * p < 1001 ; p ++ ) { // If p is not changed then it is a prime if ( arr [ p ]) { // Update all multiples of p for ( let i = p * 2 ; i < 1001 ; i = i + p ) arr [ i ] = false ; } } } function find_sphene ( N ) { var arr1 = Array ( 8 ). fill ( 0 ); // to store the 8 divisors var count = 0 ; // to count the number of divisor var j = 0 ; for ( let i = 1 ; i <= N ; i ++ ) { if ( N % i == 0 && count < 8 ) { count ++ ; arr1 [ j ++ ] = i ; } } // finally check if there re 8 divisor and // all the numbers are distinct prime no return 1 // else return 0); if ( count == 8 && ( arr [ arr1 [ 1 ]] && arr [ arr1 [ 2 ]] && arr [ arr1 [ 3 ]])) return 1 ; return 0 ; } // Driver code var n = 60 ; simpleSieve (); var ans = find_sphene ( n ); if ( ans == 1 ) document . write ( 'Yes' ); else document . write ( 'NO' ); // This code is contributed by aashish1995 < /script>
Python3 def simpleSieve (): # Initialize all entries of arr as True arr = [ True ] * 1001 # One by one traverse all numbers so that their # multiples can be marked as composite for p in range ( 2 int ( 1001 ** 0.5 ) + 1 ): # If p is not changed then it is a prime if arr [ p ]: # Update all multiples of p for i in range ( p * 2 1001 p ): arr [ i ] = False return arr def find_sphene ( N ): arr = simpleSieve () arr1 = [ 0 ] * 8 # to store the 8 divisors count = 0 # to count the number of divisors j = 0 for i in range ( 1 N + 1 ): if N % i == 0 and count < 9 : count += 1 arr1 [ j ] = i j += 1 # finally check if there are 8 divisors and all the numbers are distinct prime no return 1 # else return 0 if count == 8 and all ( arr [ arr1 [ i ]] for i in range ( 1 4 )): return 1 return 0 # Driver program to test above function if __name__ == '__main__' : n = 60 ans = find_sphene ( n ) if ans : print ( 'Yes' ) else : print ( 'No' )
Изход:
NOВремева сложност: O(?p log p)
Помощно пространство: O(n)препратки:
Създаване на тест
1. OEIS
2. https://en.wikipedia.org/wiki/Sphenic_number
