Número esfénico
Pruébalo en GfG Practice 
#practiceLinkDiv { mostrar: ninguno !importante; }
#practiceLinkDiv { mostrar: ninguno !importante; } A Número esfénico es un entero positivo norte que es un producto de exactamente tres números primos distintos. Los primeros números esfénicos son 30 42 66 70 78 102 105 110 114...
dado un numero norte determinar si es un Número Esfénico o no.
Ejemplos:
Práctica recomendada Número esfénico ¡Pruébalo!Aporte : 30
Producción : Sí
Explicación : 30 es el número esfénico más pequeño
30 = 2 × 3 × 5 el producto de los tres primos más pequeñosAporte : 60
Producción : No
Explicación : 60 = 2 2 x 3 x 5 tiene exactamente 3 factores primos pero no es un número esfénico
El número esfénico se puede comprobar por el hecho de que cada número esfénico tendrá exactamente 8 divisores. NÚMERO ESFÉNICO
Entonces, primero intentaremos encontrar si el número tiene exactamente 8 divisores; de lo contrario, la respuesta simple es no. Si hay exactamente 8 divisores entonces confirmaremos si los primeros 3 dígitos después del 1 son primos o no.
P.ej. 30 (número esfénico)
30=p*q*r(es decir, pq y r son tres números primos distintos y su producto es 30)
el conjunto del divisor es (12356101530).
A continuación se muestra la implementación de la idea.
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' )
Producción:
NOComplejidad del tiempo: O(?p Iniciar sesiónp)
Espacio Auxiliar: En)Referencias:
Crear cuestionario
1. OEIS
2. https://en.wikipedia.org/wiki/Sphenic_number
