Рубрики

Найдите первое натуральное число, факториал которого делится на x

Для заданного числа x задача состоит в том, чтобы найти первое натуральное число i, факториал которого делится на x.

Примеры :

Input  : x = 10
Output : 5
5 is the smallest number such that 
(5!) % 10 = 0

Input  : x = 16
Output : 6
6 is the smallest number such that 
(6!) % 16 = 0

Простым решением является итерация от 1 до x-1, и для каждого числа я проверяю, если я! делится на х.

C ++

// Простая программа на C ++ для поиска первого естественного
// число, факториал которого делит х.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает первое число, чей факториал
// делит х.

int firstFactorialDivisibleNumber(int x)

{

    int i = 1; // Результат

    int fact = 1;

    for (i = 1; i < x; i++) {

        fact = fact * i;

        if (fact % x == 0)

            break;

    }

  

    return i;

}

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

int main(void)

{

    int x = 16;

    cout << firstFactorialDivisibleNumber(x);

    return 0;

}

Джава

// Простая Java-программа для поиска первого естественного
// число, чей факториал делит x

class GFG {

  

    // Возвращает первое число, чей факториал

    // делит х.

    static int firstFactorialDivisibleNumber(int x)

    {

        int i = 1; // Результат

        int fact = 1;

        for (i = 1; i < x; i++) {

            fact = fact * i;

            if (fact % x == 0)

                break;

        }

  

        return i;

    }

  

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

    public static void main(String[] args)

    {

        int x = 16;

        System.out.print(firstFactorialDivisibleNumber(x));

    }

}

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

python3

# Простая программа на Python для поиска
# первый натуральный номер которого
# факториал делит х.

  
# Возвращает первый номер которого
# факториал делит х.

def firstFactorialDivisibleNumber(x):

    i = 1; # Результат

    fact = 1;

    for i in range(1, x):

        fact = fact * i

        if (fact % x == 0):

            break

    return i

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

x = 16

print(firstFactorialDivisibleNumber(x))

  
# Этот код добавлен
# by 29AjayKumar

C #

// Простая программа на C # для поиска первого естественного
// число, чей факториал делит x

using System;

  

class GFG {

  

    // Возвращает первое число, чей факториал

    // делит х.

    static int firstFactorialDivisibleNumber(int x)

    {

        int i = 1; // Результат

        int fact = 1;

        for (i = 1; i < x; i++) {

            fact = fact * i;

            if (fact % x == 0)

                break;

        }

  

        return i;

    }

  

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

    public static void Main()

    {

        int x = 16;

  

        Console.Write(

            firstFactorialDivisibleNumber(x));

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// Простая PHP-программа для поиска
// первый натуральный номер которого
// факториал делит х.

  
// Возвращает первый номер которого
// факториал делит х.

function firstFactorialDivisibleNumber($x)

{

    // Результат

    $i = 1; 

    $fact = 1;

    for ($i = 1; $i < $x; $i++) 

    {

        $fact = $fact * $i;

        if ($fact % $x == 0)

            break;

    }

  

    return $i;

}

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

$x = 16;

echo(firstFactorialDivisibleNumber($x));

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


Выход :

6

Если бы мы применили этот наивный подход, мы бы не пошли выше 20! или 21! (long long int будет иметь свой верхний предел).

Лучшее решение позволяет избежать переполнения. Решение основано на следующих наблюдениях.

  • Если я! делится на x, то (i + 1) !, (i + 2) !,… также делятся на x.
  • Для числа x все факториалы i! делятся на х, когда я> = х.
  • Если число x простое, то ни один факториал ниже x не может разделить его, поскольку x не может быть сформировано с умножением меньших чисел.

Ниже приведен алгоритм

1) Run a loop for i = 1 to n-1
       
   a) Remove common factors
      new_x /= gcd(i, new_x);

   b) Check if we found first i.
      if (new_x == 1)
          break;

2) Return i

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

CPP

// C ++ программа для поиска первого натурального числа
// чей факториал делит х.
#include <bits/stdc++.h>

using namespace std;

  
// GCD функция для вычисления наибольшего
// делитель между а и б

int gcd(int a, int b)

{

    if ((a % b) == 0)

        return b;

    return gcd(b, a % b);

}

  
// Возвращает первое число, чей факториал
// делит х.

int firstFactorialDivisibleNumber(int x)

{

    int i = 1; // Результат

    int new_x = x;

  

    for (i = 1; i < x; i++) {

        // Удалить общие факторы

        new_x /= gcd(i, new_x);

  

        // Сначала мы нашли

        if (new_x == 1)

            break;

    }

    return i;

}

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

int main(void)

{

    int x = 16;

    cout << firstFactorialDivisibleNumber(x);

    return 0;

}

Джава

// Эффективная Java-программа для поиска первой
// натуральное число, факториал которого делит x.

class GFG {

  

    // GCD функция для вычисления наибольшего

    // делитель между а и б

    static int gcd(int a, int b)

    {

        if ((a % b) == 0)

            return b;

        return gcd(b, a % b);

    }

  

    // Возвращает первое число, чей факториал

    // делит х.

    static int firstFactorialDivisibleNumber(int x)

    {

        int i = 1; // Результат

        int new_x = x;

  

        for (i = 1; i < x; i++) {

  

            // Удалить общие факторы

            new_x /= gcd(i, new_x);

  

            // Сначала мы нашли

            if (new_x == 1)

                break;

        }

        return i;

    }

  

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

    public static void main(String[] args)

    {

        int x = 16;

        System.out.print(firstFactorialDivisibleNumber(x));

    }

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

python3

      
# Python3 программа для поиска первого натурального числа
# чей факториал делит х.

  

   
# GCD функция для вычисления наибольшего
# делитель между а и б

def gcd(a,  b):

    if ((a % b) == 0):

        return b

    return gcd(b, a % b)

  

   
# Возвращает первое число, чей факториал
# делит х.

def firstFactorialDivisibleNumber(x):

    i = 1 # Результат

    new_x = x

   

    for i in range(1,x):

        # Удалить общие факторы

        new_x /= gcd(i, new_x)

   

        # Мы нашли сначала я.

        if (new_x == 1):

            break

    return i

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

def main():

    x = 16

    print(firstFactorialDivisibleNumber(x))

  

if __name__ == '__main__':

    main()

  
# Этот код предоставлен 29AjayKumar

C #

// Эффективная программа на C # для поиска
// натуральное число, факториал которого
// делит х.

using System;

  

class GFG {

  

    // GCD функция для вычисления

    // Наибольший делитель среди

    // и б

    static int gcd(int a, int b)

    {

        if ((a % b) == 0)

            return b;

        return gcd(b, a % b);

    }

  

    // Возвращает первый номер которого

    // факториал делит х.

    static int firstFactorialDivisibleNumber(

                                        int x)

    {

        int i = 1; // Результат

        int new_x = x;

  

        for (i = 1; i < x; i++) {

  

            // Удалить общие факторы

            new_x /= gcd(i, new_x);

  

            // Сначала мы нашли

            if (new_x == 1)

                break;

        }

          

        return i;

    }

  

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

    public static void Main()

    {

        int x = 16;

        Console.Write(

            firstFactorialDivisibleNumber(x));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

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

  
// GCD функция для вычисления
// Наибольший делитель среди а и б

function gcd($a, $b)

{

    if (($a % $b) == 0)

        return $b;

    return gcd($b, $a % $b);

}

  
// Возвращает первое число
// чей факториал делит х.

function firstFactorialDivisibleNumber($x)

{

    // Результат

    $i = 1; 

    $new_x = $x;

  

    for ($i = 1; $i < $x; $i++) 

    {

        // Удалить общие факторы

        $new_x /= gcd($i, $new_x);

  

        // Сначала мы нашли

        if ($new_x == 1)

            break;

    }

    return $i;

}

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

$x = 16;

echo(firstFactorialDivisibleNumber($x));

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

Выход :

6

Другой подход с использованием библиотеки Boost:
(Спасибо ajay0007 за содействие этому подходу)
Здесь мы используем библиотеку boost для эффективного вычисления значения факториала.
Предварительное условие : boost-multiprecision-library

C ++

// Cpp программа для поиска
// Специальный факторный номер
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

  

using boost::multiprecision::cpp_int;

using namespace std;

  
// функция для расчета факто

cpp_int fact(int n)

{

    cpp_int num = 1;

      

    for (int i = 1; i <= n; i++)

        num = num * i;

      

    return num;

}

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

int Special_Factorial_Number(int k)

{

      

    for(int i = 1 ; i <= k ; i++ )

    

        // вызов функции факта и

        // по модулю с к и проверить

        // если условие ИСТИНА, то вернуть i

        if ( ( fact (i) % k ) == 0 )

        {

            return i;

        }

    }

}

  
// функция драйвера

int main()

{

    // принимая вход

    int k = 16;

      

    cout<<Special_Factorial_Number(k);

}

Джава

// Java программа для поиска
// Специальный факторный номер

public class GFG {

  
// функция для расчета факто

    static int fact(int n) {

        int num = 1;

  

        for (int i = 1; i <= n; i++) {

            num = num * i;

        }

  

        return num;

    }

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

    static int Special_Factorial_Number(int k) {

  

        for (int i = 1; i <= k; i++) {

            // вызов функции факта и

            // по модулю с к и проверить

            // если условие ИСТИНА, то вернуть i

            if (fact(i) % k == 0) {

                return i;

            }

        }

        return 0;

    }

  
// функция драйвера

    public static void main(String[] args) {

        // принимая вход

        int k = 16;

        System.out.println(Special_Factorial_Number(k));

  

    }

}

  
/ * Этот код предоставлен Rajput-Ji * /

python3

# Python 3 программа для поиска
# Специальный Факториальный Номер

  
# функция для расчета факто

def fact( n):

    num = 1

    for i in range(1, n + 1):

        num = num * i

    return num

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

def Special_Factorial_Number(k):

      

    for i in range(1, k + 1):

          

        # функция факта вызова и

        # По модулю с к и проверить

        # если условие ИСТИНА, тогда вернуть i

        if (fact(i) % k == 0):

            return i

    return 0

  
Код водителя

if __name__ == '__main__':

      

    # принимая вход

    k = 16

    print(Special_Factorial_Number(k))

  
# Этот код предоставлен Rajput-Ji

C #

// C # программа для поиска
// Специальный факторный номер

using System; 

public class GFG{

  

  
// функция для расчета факто

    static int fact(int n) { 

        int num = 1; 

  

        for (int i = 1; i <= n; i++) { 

            num = num * i; 

        

  

        return num; 

    

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

    static int Special_Factorial_Number(int k) { 

  

        for (int i = 1; i <= k; i++) { 

            // вызов функции факта и

            // по модулю с к и проверить

            // если условие ИСТИНА, то вернуть i

            if (fact(i) % k == 0) { 

                return i; 

            

        

        return 0; 

    

  
// функция драйвера

    public static void Main() { 

        // принимая вход

        int k = 16; 

        Console.WriteLine(Special_Factorial_Number(k)); 

  

    

  
// Этот код предоставлен 29AjayKumar

PHP

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

  
// функция для расчета
// фактоил

function fact($n)

{

    $num = 1;

      

    for ($i = 1; $i <= $n; $i++)

        $num = $num * $i;

      

    return $num;

}

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

function Special_Factorial_Number($k)

{

      

    for($i = 1 ; $i <= $k ; $i++ )

    

          

        // вызов функции факта и

        // по модулю с к и проверить

        // если условие ИСТИНА

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

        if (( fact ($i) % $k ) == 0 )

        {

            return $i;

        }

    }

}

  

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

    $k = 16;

    echo Special_Factorial_Number($k);

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


Выход :

6

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

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

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

Найдите первое натуральное число, факториал которого делится на x

0.00 (0%) 0 votes