Eine brillante Zahl ist eine Zahl N , die das Produkt zweier Primzahlen mit der gleichen Anzahl von Ziffern ist.
Einige brillante Zahlen sind: 

4, 6, 9, 10, 14, 15, 21, 25, 35, 49…. 

Prüfen Sie, ob N eine brillante Zahl ist

Bei einer gegebenen Zahl N besteht die Aufgabe darin, zu prüfen, ob N eine brillante Zahl ist oder nicht. Wenn N eine brillante Zahl ist, dann drucke „Ja“ , andernfalls drucke „Nein“ .
Beispiele: 

Eingabe: N = 1711 
Ausgabe: Ja 
Erklärung: 
1711 = 29*59 und sowohl 29 als auch 59 sind zweistellig.
Eingang: N = 16 
Ausgang: Nein 

Ansatz: Die Idee ist, alle Primzahlen kleiner oder gleich der gegebenen Zahl N mit Sieve of Eratosthenes zu finden . Sobald wir ein Array haben, das alle Primzahlen angibt, können wir dieses Array durchlaufen, um ein Paar mit einem bestimmten Produkt zu finden. Wir werden mit dem Sieb von Eratosthenes zwei Primzahlen mit gegebenem Produkt finden und prüfen, ob das Paar die gleiche Anzahl von Ziffern hat oder nicht.
Unten ist die Implementierung des obigen Ansatzes:
 

C++

// C++ implementation for the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate all prime
// numbers less than n
bool SieveOfEratosthenes(int n,
                bool isPrime[])
{
    // Initialize all entries of
    // boolean array as true.
    // A value in isPrime[i]
    // will finally be false
    // if i is Not a prime
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++)
        isPrime[i] = true;
 
    for (int p = 2; p * p <= n; p++) {
 
        // If isPrime[p] is not changed,
        // then it is a prime
        if (isPrime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                isPrime[i] = false;
        }
    }
}
 
// Function to return the number
// of digits in a number
int countDigit(long long n)
{
    return floor(log10(n) + 1);
}
 
// Function to check if N is a
// Brilliant number
bool isBrilliant(int n)
{
    int flag = 0;
 
    // Generating primes using Sieve
    bool isPrime[n + 1];
    SieveOfEratosthenes(n, isPrime);
 
    // Traversing all numbers
    // to find first pair
    for (int i = 2; i < n; i++) {
        int x = n / i;
 
        if (isPrime[i] &&
          isPrime[x] and x * i == n) {
            if (countDigit(i) == countDigit(x))
                return true;
        }
    }
 
    return false;
}
 
// Driver Code
int main()
{
    // Given Number
    int n = 1711;
 
    // Function Call
    if (isBrilliant(n))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Java

// Java implementation for the
// above approach
import java.util.*;
class GFG{
 
// Function to generate all prime
// numbers less than n
static void SieveOfEratosthenes(int n,
                    boolean isPrime[])
{
    // Initialize all entries of
    // boolean array as true.
    // A value in isPrime[i]
    // will finally be false
    // if i is Not a prime
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++)
        isPrime[i] = true;
 
    for (int p = 2; p * p <= n; p++)
    {
 
        // If isPrime[p] is not changed,
        // then it is a prime
        if (isPrime[p] == true)
        {
 
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                isPrime[i] = false;
        }
    }
}
 
// Function to return the number
// of digits in a number
static int countDigit(int n)
{
    int count = 0;
        while (n != 0)
        {
            n = n / 10;
            ++count;
        }
        return count;
}
 
// Function to check if N is a
// Brilliant number
static boolean isBrilliant(int n)
{
    int flag = 0;
 
    // Generating primes using Sieve
    boolean isPrime[] = new boolean[n + 1];
    SieveOfEratosthenes(n, isPrime);
 
    // Traversing all numbers
    // to find first pair
    for (int i = 2; i < n; i++)
    {
        int x = n / i;
 
        if (isPrime[i] &&
        isPrime[x] && (x * i) == n)
        {
            if (countDigit(i) == countDigit(x))
                return true;
        }
    }
    return false;
}
 
// Driver Code
public static void main (String[] args)
{
    // Given Number
    int n = 1711;
 
    // Function Call
    if (isBrilliant(n))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by Ritik Bansal

Python3

# Python3 program for the
# above approach
import math
 
# Function to generate all prime
# numbers less than n
def SieveOfEratosthenes(n, isPrime):
     
    # Initialize all entries of 
    # boolean array as true. 
    # A value in isPrime[i] 
    # will finally be false 
    # if i is Not a prime
    isPrime[0] = isPrime[1] = False
     
    for i in range(2, n + 1, 1):
        isPrime[i] = True
   
    p = 2
    while(p * p <= n ):
   
        # If isPrime[p] is not changed, 
        # then it is a prime
        if (isPrime[p] == True):
   
            # Update all multiples of p
            for i in range(p * 2, n + 1, p):
                isPrime[i] = False
         
        p += 1
   
# Function to return the number
# of digits in a number
def countDigit(n):
     
    return math.floor(math.log10(n) + 1)
   
# Function to check if N is a
# Brilliant number
def isBrilliant(n):
     
    flag = 0
   
    # Generating primes using Sieve
    isPrime = [0] * (n + 1)
    SieveOfEratosthenes(n, isPrime)
   
    # Traversing all numbers
    # to find first pair
    for i in range(2, n, 1):
        x = n // i
   
        if (isPrime[i] and 
            isPrime[x] and x * i == n):
            if (countDigit(i) == countDigit(x)):
                return True   
   
    return False 
   
# Driver Code
 
# Given Number
n = 1711
   
# Function Call
if (isBrilliant(n)):
    print("Yes")
else:
    print("No")
     
# This code is contributed by sanjoy_62

C#

// C# implementation for the
// above approach
using System;
class GFG{
 
// Function to generate all prime
// numbers less than n
static void SieveOfEratosthenes(int n,
                       bool []isPrime)
{
     
    // Initialize all entries of
    // boolean array as true.
    // A value in isPrime[i]
    // will finally be false
    // if i is Not a prime
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i <= n; i++)
       isPrime[i] = true;
 
    for(int p = 2; p * p <= n; p++)
    {
         
       // If isPrime[p] is not changed,
       // then it is a prime
       if (isPrime[p] == true)
       {
            
           // Update all multiples of p
           for(int i = p * 2; i <= n; i += p)
              isPrime[i] = false;
       }
    }
}
 
// Function to return the number
// of digits in a number
static int countDigit(int n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}
 
// Function to check if N is a
// Brilliant number
static bool isBrilliant(int n)
{
    //int flag = 0;
 
    // Generating primes using Sieve
    bool []isPrime = new bool[n + 1];
    SieveOfEratosthenes(n, isPrime);
 
    // Traversing all numbers
    // to find first pair
    for(int i = 2; i < n; i++)
    {
       int x = n / i;
        
       if (isPrime[i] &&
           isPrime[x] && (x * i) == n)
       {
           if (countDigit(i) == countDigit(x))
               return true;
       }
    }
    return false;
}
 
// Driver Code
public static void Main()
{
    // Given Number
    int n = 1711;
 
    // Function Call
    if (isBrilliant(n))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
// Javascript implementation for the
// above approach
 
 
    // Function to generate all prime
    // numbers less than n
    function SieveOfEratosthenes( n, isPrime) {
        // Initialize all entries of
        // let array as true.
        // A value in isPrime[i]
        // will finally be false
        // if i is Not a prime
        isPrime[0] = isPrime[1] = false;
        for ( let i = 2; i <= n; i++)
            isPrime[i] = true;
 
        for (let  p = 2; p * p <= n; p++) {
 
            // If isPrime[p] is not changed,
            // then it is a prime
            if (isPrime[p] == true) {
 
                // Update all multiples of p
                for (let  i = p * 2; i <= n; i += p)
                    isPrime[i] = false;
            }
        }
    }
 
    // Function to return the number
    // of digits in a number
    function countDigit( n) {
        let count = 0;
        while (n != 0) {
            n = parseInt(n / 10);
            ++count;
        }
        return count;
    }
 
    // Function to check if N is a
    // Brilliant number
    function isBrilliant( n) {
        let flag = 0;
 
        // Generating primes using Sieve
        let isPrime = Array(n + 1).fill(true);
        SieveOfEratosthenes(n, isPrime);
 
        // Traversing all numbers
        // to find first pair
        for ( let i = 2; i < n; i++) {
            let x = n / i;
 
            if (isPrime[i] && isPrime[x] && (x * i) == n) {
                if (countDigit(i) == countDigit(x))
                    return true;
            }
        }
        return false;
    }
 
    // Driver Code
      
        // Given Number
        let n = 1711;
 
        // Function Call
        if (isBrilliant(n))
            document.write("Yes");
        else
            document.write("No");
 
// This code contributed by Rajput-Ji
 
</script>
Ausgabe: 
ja

 

Zeitkomplexität: O(n)

Hilfsraum: O(n)

Referenz: http://oeis.org/A078972
 

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .