Рубрики

Мощный номер

Число n называется мощным числом, если для каждого простого множителя p его p 2 также делит его. Например: — 36 — это мощное число. Он делится на 3 и квадрат 3, т. Е. 9.

Первые несколько мощных чисел:
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64….

Учитывая число n, наша задача состоит в том, чтобы проверить, является ли это мощным или нет.
Примеры :

Input: 27
Output: YES

Input: 32
Output: YES

Input: 12
Output: NO

Идея основана на том факте, что если число n является мощным, то все его простые множители и их квадраты должны делиться на n. Мы находим все простые факторы данного числа . И для каждого простого фактора мы находим высшую степень его, которая делит n. Если мы найдем главный фактор с наивысшей делительной степенью 1, мы вернем false. Если наибольшая делительная сила всех основных факторов больше 1, мы возвращаем true.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа, чтобы найти, является ли число мощным или нет.
#include <bits/stdc++.h>

using namespace std;

  
// функция, чтобы проверить, является ли число сильным

bool isPowerful(int n)

{

    // Сначала делим число повторно на 2

    while (n % 2 == 0) {

        int power = 0;

        while (n % 2 == 0) {

            n /= 2;

            power++;

        }

  

        // Если только 2 ^ 1 делит n (не высшие степени),

        // затем возвращаем false

        if (power == 1)

            return false;

    }

  

    // если n не является степенью 2, то этот цикл будет выполнен

    // повторить вышеописанный процесс

    for (int factor = 3; factor <= sqrt(n); factor += 2) {

        // Находим наибольшую степень "фактора", который делит n

        int power = 0;

        while (n % factor == 0) {

            n = n / factor;

            power++;

        }

  

        // Если только множитель ^ 1 делит n (не высшие степени),

        // затем возвращаем false

        if (power == 1)

            return false;

    }

  

    // n должно быть 1 сейчас, если это не простое число.

    // Поскольку простые числа не являются сильными, мы возвращаем

    // ложь, если n не 1.

    return (n == 1);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    isPowerful(20) ? cout << "YES\n" : cout << "NO\n";

    isPowerful(27) ? cout << "YES\n" : cout << "NO\n";

  

    return 0;

}

Джава

// Java-программа для поиска
// номер мощный или нет.

  

class GFG {

    // функция для проверки

    // число мощное

    static boolean isPowerful(int n)

    {

        // Сначала делим число

        // повторно на 2

        while (n % 2 == 0) {

            int power = 0;

            while (n % 2 == 0) {

                n /= 2;

                power++;

            }

  

            // Если только 2 ^ 1 делит n (не высшие степени),

            // затем возвращаем false

            if (power == 1)

                return false;

        }

  

        // если n не является степенью 2, то этот цикл будет выполнен

        // повторить вышеописанный процесс

        for (int factor = 3; factor <= Math.sqrt(n); factor += 2) {

            // Находим наибольшую степень "фактора", который делит n

            int power = 0;

            while (n % factor == 0) {

                n = n / factor;

                power++;

            }

  

            // Если только множитель ^ 1 делит n (не высшие степени),

            // затем возвращаем false

            if (power == 1)

                return false;

        }

  

        // n должно быть 1 сейчас, если это не простое число.

        // Поскольку простые числа не являются сильными, мы возвращаем

        // ложь, если n не 1.

        return (n == 1);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        if (isPowerful(20))

            System.out.print("YES\n");

        else

            System.out.print("NO\n");

        if (isPowerful(27))

            System.out.print("YES\n");

        else

            System.out.print("NO\n");

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python программа для поиска
# если число является сильным или нет.

import math

  
# функция, чтобы проверить, если
# номер мощный

def isPowerful(n):

  

    # Сначала разделите число несколько раз на 2

    while (n % 2 == 0):

  

        power = 0

        while (n % 2 == 0):

          

            n = n//2 

            power = power + 1

          

           

        # Если только 2 ^ 1 делит

        # n (не высшие силы),

        # затем вернуть false

        if (power == 1):

            return False

      

   

    # если n не является степенью 2

    # тогда этот цикл будет выполнен

    # повторить вышеописанный процесс

    for factor in range(3, int(math.sqrt(n))+1, 2):

      

        # Найти высшую силу

        # «фактор», который делит n

        power = 0

        while (n % factor == 0):

          

            n = n//factor

            power = power + 1

          

   

        # Если только множитель ^ 1 делит

        # n (не высшие силы),

        # затем вернуть false

        if (power == 1):

            return false

      

   

     # n должно быть 1 сейчас, если оно

     # не является простым числом.

     # Так как простые числа

     # не мощно, мы возвращаемся

     # false, если n не равно 1.

    return (n == 1)

  
# Код драйвера

  

print("YES" if isPowerful(20) else "NO")

print("YES" if isPowerful(27) else "NO")

  

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа, чтобы найти, если
// номер мощный или нет.

using System;

  

class GFG {

  

    // функция для проверки

    // число мощное

    static bool isPowerful(int n)

    {

        // Сначала делим число

        // повторно на 2

        while (n % 2 == 0) {

            int power = 0;

            while (n % 2 == 0) {

                n /= 2;

                power++;

            }

  

            // Если только 2 ^ 1 делит n

            // (не высшие силы),

            // затем возвращаем false

            if (power == 1)

                return false;

        }

  

        // если n не является степенью 2, то

        // этот цикл выполнит повтор

        // вышеуказанный процесс

        for (int factor = 3; factor <= Math.Sqrt(n); factor += 2) {

            // Найти наибольшую силу "фактора"

            // который делит n

            int power = 0;

            while (n % factor == 0) {

                n = n / factor;

                power++;

            }

  

            // Если только множитель ^ 1 делит n

            // (не высшие силы), тогда

            // вернуть ложь

            if (power == 1)

                return false;

        }

  

        // n должно быть 1 сейчас, если это не так

        // простое число.

        // Поскольку простые числа не

        // мощный, мы возвращаем false, если

        // n не 1.

        return (n == 1);

    }

  

    // Код драйвера

    public static void Main()

    {

        if (isPowerful(20))

            Console.WriteLine("YES");

        else

            Console.WriteLine("NO");

  

        if (isPowerful(27))

            Console.WriteLine("YES");

        else

            Console.WriteLine("NO");

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для поиска
// номер сильный или нет

  
// функция для проверки
// число мощное

function isPowerful($n)

{

    // Сначала делим

    // номер многократно по 2

    while ($n % 2 == 0)

    {

        $power = 0;

        while ($n % 2 == 0)

        {

            $n /= 2;

            $power++;

        }

          

        // Если только 2 ^ 1 делит

        // n (не высшие силы),

        // затем возвращаем false

        if ($power == 1)

        return false;

    }

  

    // если n не является степенью 2

    // тогда этот цикл будет выполнен

    // повторить вышеописанный процесс

    for ($factor = 3; 

         $factor <= sqrt($n); 

         $factor += 2)

    {

        // Найти наибольшую силу

        // «фактор», который делит n

        $power = 0;

        while ($n % $factor == 0)

        {

            $n = $n / $factor;

            $power++;

        }

  

        // Если только множитель ^ 1 делит

        // n (не высшие силы),

        // затем возвращаем false

        if ($power == 1)

        return false;

    }

  

    // n должно быть 1 сейчас, если это

    // не простое число. поскольку

    // простые числа не являются сильными,

    // мы возвращаем false, если n не равно 1.

    return ($n == 1);

}

  
// Код драйвера

$d = isPowerful(20) ? 

            "YES\n"

              "NO\n";

    echo $d;

$d = isPowerful(27) ? 

            "YES\n"

              "NO\n";

    echo $d;

  
// Этот код предоставлен ajit.
?>


Выход :

NO
YES

Ссылки:
https://en.wikipedia.org/wiki/Powerful_number

Эта статья предоставлена Суровым Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Мощный номер

0.00 (0%) 0 votes