Sfénické číslo
Zkuste to na GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } A Sfénické číslo je kladné celé číslo n který je součinem přesně tří různých prvočísel. Prvních několik sférických čísel je 30 42 66 70 78 102 105 110 114 ...
Dané číslo n určit, zda se jedná o sférické číslo nebo ne.
Příklady:
Doporučená praxe Sfénické číslo Zkuste to!Vstup : 30
Výstup : Ano
Vysvětlení : 30 je nejmenší sférické číslo
30 = 2 × 3 × 5 součin nejmenších tří prvočísel
Vstup : 60
Výstup : Ne
Vysvětlení : 60 = 2 2 x 3 x 5 má přesně 3 prvočísla, ale není to sférické číslo
Sfénové číslo lze zkontrolovat tak, že každé sférické číslo bude mít právě 8 dělitelů SFÉNICKÉ ČÍSLO
Nejprve se tedy pokusíme zjistit, zda má číslo přesně 8 dělitelů, pokud ne, pak je jednoduchá odpověď ne. Pokud je dělitelů přesně 8, potvrdíme, zda první 3 číslice po 1 jsou prvočísla nebo ne.
Např. 30 (kulové číslo)
30=p*q*r(tj. pq a r jsou tři různá prvočísla a jejich součin je 30)
množina dělitele je (12356101530).
Níže je realizace nápadu.
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' )
výstup:
NOČasová náročnost: O(?p log p)
Pomocný prostor: Na)Reference:
Vytvořit kvíz
1. OEIS
2. https://cs.wikipedia.org/wiki/Sphenic_number
