Как быстро найти факториал большого числа

#include <iostream>

using namespace std;

#define MAX 500

int multiply(int x, int res[], int res_size);

void factorial(int n)

{

    int res[MAX];

    res[0] = 1;

    int res_size = 1;

    for (int x = 2; x <= n; x++)

        res_size = multiply(x, res, res_size);

    cout << "Factorial of given number is n";

    for (int i = res_size - 1; i >= 0; i--)

        cout << res[i];

}

int multiply(int x, int res[], int res_size)

{

    int carry = 0;

    for (int i = 0; i < res_size; i++) {

        int prod = res[i] * x + carry;

        res[i] = prod % 10;

        carry = prod / 10;

    }

    while (carry) {

        res[res_size] = carry % 10;

        carry = carry / 10;

        res_size++;

    }

    return res_size;

}

int main()

{

    factorial(100);

    return 0;

}

class GFG {

    static void factorial(int n)

    {

        int res[] = new int[500];

        res[0] = 1;

        int res_size = 1;

        for (int x = 2; x <= n; x++)

            res_size = multiply(x, res, res_size);

        System.out.println("Factorial of given number is ");

        for (int i = res_size - 1; i >= 0; i--)

            System.out.print(res[i]);

    }

    static int multiply(int x, int res[], int res_size)

    {

        int carry = 0;

        for (int i = 0; i < res_size; i++) {

            int prod = res[i] * x + carry;

            res[i] = prod % 10;

            carry = prod / 10;

        }

        while (carry != 0) {

            res[res_size] = carry % 10;

            carry = carry / 10;

            res_size++;

        }

        return res_size;

    }

    public static void main(String args[])

    {

        factorial(100);

    }

}

import sys

def factorial(n):

    res = [None]*500

    res[0] = 1

    res_size = 1

    x = 2

    while x <= n:

        res_size = multiply(x, res, res_size)

        x = x + 1

    print("Factorial of given number is")

    i = res_size-1

    while i >= 0:

        sys.stdout.write(str(res[i]))

        sys.stdout.flush()

        i = i - 1

def multiply(x, res, res_size):

    carry = 0 

    i = 0

    while i < res_size:

        prod = res[i] * x + carry

        res[i] = prod % 10 

        carry = prod//10 

        i = i + 1

    while (carry):

        res[res_size] = carry % 10

        carry = carry // 10

        res_size = res_size + 1

    return res_size

factorial(100)

using System;

class GFG {

    static void factorial(int n)

    {

        int[] res = new int[500];

        res[0] = 1;

        int res_size = 1;

        for (int x = 2; x <= n; x++)

            res_size = multiply(x, res, res_size);

        Console.WriteLine("Factorial of "

                          + "given number is ");

        for (int i = res_size - 1; i >= 0; i--)

            Console.Write(res[i]);

    }

    static int multiply(int x, int[] res, int res_size)

    {

        int carry = 0;

        for (int i = 0; i < res_size; i++) {

            int prod = res[i] * x + carry;

            res[i] = prod % 10;

            carry = prod / 10;

        }

        while (carry != 0) {

            res[res_size] = carry % 10;

            carry = carry / 10;

            res_size++;

        }

        return res_size;

    }

    static public void Main() { factorial(100); }

}

<?php

$MAX = 500;

function factorial($n)

{

    global $MAX;

    $res = array_fill(0, $MAX, 0);

    $res[0] = 1;

    $res_size = 1;

    for ($x = 2; $x <= $n; $x++)

        $res_size = multiply($x, $res, $res_size);

    echo "Factorial of given number is n";

    for ($i = $res_size - 1; $i >= 0; $i--)

        echo $res[$i];

}

function multiply($x, &$res, $res_size)

{

    $carry = 0;

    for ($i = 0; $i < $res_size; $i++)

    {

        $prod = $res[$i] * $x + $carry;

        $res[$i] = $prod % 10;

        $carry = (int)($prod / 10);

    }

    while ($carry)

    {

        $res[$res_size] = $carry % 10;

        $carry = (int)($carry / 10);

        $res_size++;

    }

    return $res_size;

}

factorial(100);

?>

<script>

function factorial(n)

{

    let res = new Array(500);

    res[0] = 1;

    let res_size = 1;

    for (let x=2; x<=n; x++)

        res_size = multiply(x, res, res_size);

    document.write("Factorial of given number is " + "<br>");

    for (let i=res_size-1; i>=0; i--)

        document.write(res[i]);

}

function multiply(x, res, res_size)

{

    let carry = 0;

    for (let i=0; i<res_size; i++)

    {

        let prod = res[i] * x + carry;

        res[i] = prod % 10;

        carry = Math.floor(prod/10);

    }

    while (carry)

    {

        res[res_size] = carry%10;

        carry = Math.floor(carry/10);

        res_size++;

    }

    return res_size;

}

    factorial(100);

</script>

#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long

ull factorial(int N)

{

    ull f = 1;

    for (ull i = 2; i <= N; i++)

        f *= i;

    return f;

}

int main()

{

    int N = 20;

    cout << factorial(N) << endl;

}

import java.math.BigInteger;

import java.util.Scanner;

public class Example {

    static BigInteger factorial(int N)

    {

        BigInteger f

            = new BigInteger("1");

        for (int i = 2; i <= N; i++)

            f = f.multiply(BigInteger.valueOf(i));

        return f;

    }

    public static void main(String args[]) throws Exception

    {

        int N = 20;

        System.out.println(factorial(N));

    }

}

def factorial(N):

    f =  1 

    for i in range(2, N + 1):

        f *= i

    return f;

N = 20;

print(factorial(N));

using System;

using System.Collections.Generic;

using System.Numerics;

public class Example {

  static BigInteger factorial(int N)

  {

    BigInteger f

      = new BigInteger(1);

    for (int i = 2; i <= N; i++)

      f = BigInteger.Multiply(f, new BigInteger(i));

    return f;

  }

  public static void Main(string[] args)

  {

    int N = 20;

    Console.WriteLine(factorial(N));

  }

}

function factorial(N)

{

let f =  BigInt(1);

for (var i = 2; i <= N; i++)

    f *= BigInt(i);

return f;

}

let N = 20;

console.log(factorial(N));

#include <iostream>

#include <vector>

using namespace std;

vector<int> multiply(vector<int>& digits, int factor) {

    int carry = 0;

    for (int i = 0; i < digits.size(); i++) {

        int prod = digits[i] * factor + carry;

        digits[i] = prod % 10;

        carry = prod / 10;

    }

    while (carry) {

        digits.push_back(carry % 10);

        carry /= 10;

    }

    return digits;

}

void print(vector<int>& digits) {

    for (int i = digits.size() - 1; i >= 0; i--) {

        cout << digits[i];

    }

}

int main() {

    int n = 100;

    vector<int> digits;

    digits.push_back(1);

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

        digits = multiply(digits, i);

    }

    print(digits);

    return 0;

}

import java.math.BigInteger;

public class Main {

    public static void main(String[] args) {

        int n = 100;

        BigInteger result = BigInteger.valueOf(1);

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

            result = result.multiply(BigInteger.valueOf(i));

        }

        System.out.println(result);

    }

}

import math

n = 100

result = math.factorial(n)

print(result)

function factorial(n) {

  let result = BigInt(1);

  for (let i = 2; i <= n; i++) {

    result *= BigInt(i);

  }

  return result;

}

const n = 100;

const result = factorial(n);

console.log(result);

using System;

using System.Collections.Generic;

class MainClass {

    static List<int> Multiply(List<int> digits, int factor)

    {

        int carry = 0;

        for (int i = 0; i < digits.Count; i++) {

            int prod = digits[i] * factor + carry;

            digits[i] = prod % 10;

            carry = prod / 10;

        }

        while (carry > 0) {

            digits.Add(carry % 10);

            carry /= 10;

        }

        return digits;

    }

    static void Print(List<int> digits)

    {

        for (int i = digits.Count - 1; i >= 0; i--) {

            Console.Write(digits[i]);

        }

    }

    static void Main()

    {

        int n = 100;

        List<int> digits = new List<int>();

        digits.Add(1);

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

            digits = Multiply(digits, i);

        }

        Print(digits);

    }

}

#статьи

• 19 май 2023
• 
  0

Что такое факториал и как его вычислить

Статья, после которой вы начнёте щёлкать факториалы как орешки.

using System;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections.Generic;
using System.Collections.Specialized;

namespace BigInt
{
    class Program
    {

        static BigInteger FactNaive(int n)
        {
            BigInteger r = 1;
            for (int i = 2; i <= n; ++i)
                r *= i;
            return r;
        }

        static BigInteger ProdTree(int l, int r)
        {
            if (l > r)
                return 1;
            if (l == r)
                return l;
            if (r - l == 1)
                return (BigInteger)l * r;
            int m = (l + r) / 2;
            return ProdTree(l, m) * ProdTree(m + 1, r);
        }

        static BigInteger FactTree(int n)
        {
            if (n < 0)
                return 0;
            if (n == 0)
                return 1;
            if (n == 1 || n == 2)
                return n;
            return ProdTree(2, n);
        }

        static BigInteger FactFactor(int n)
        {
            if (n < 0)
                return 0;
            if (n == 0)
                return 1;
            if (n == 1 || n == 2)
                return n;
            bool[] u = new bool[n + 1];
            List<Tuple<int, int>> p = new List<Tuple<int, int>>();
            for (int i = 2; i <= n; ++i)
                if (!u[i])
                {
                    int k = n / i;
                    int c = 0;
                    while (k > 0)
                    {
                        c += k;
                        k /= i;
                    }
                    p.Add(new Tuple<int, int>(i, c));
                    int j = 2;
                    while (i * j <= n)
                    {
                        u[i * j] = true;
                        ++j;
                    }
                }
            BigInteger r = 1;
            for (int i = p.Count() - 1; i >= 0; --i)
                r *= BigInteger.Pow(p[i].Item1, p[i].Item2);
            return r;
        }

        static void Main(string[] args)
        {
            int n;
            int t;

            Console.Write("n = ");
            n = Convert.ToInt32(Console.ReadLine());

            t = Environment.TickCount;
            BigInteger fn = FactNaive(n);
            Console.WriteLine("Naive time: {0} ms", Environment.TickCount - t);

            t = Environment.TickCount;
            BigInteger ft = FactTree(n);
            Console.WriteLine("Tree time: {0} ms", Environment.TickCount - t);

            t = Environment.TickCount;
            BigInteger ff = FactFactor(n);
            Console.WriteLine("Factor time: {0} ms", Environment.TickCount - t);

            Console.WriteLine("Check: {0}", fn == ft && ft == ff ? "ok" : "fail");
        }
    }
}

#include <iostream>
#include <ctime>
#include <vector>
#include <utility>

#include <gmpxx.h>

using namespace std;

mpz_class FactNaive(int n)
{
	mpz_class r = 1;
	for (int i = 2; i <= n; ++i)
		r *= i;
	return r;
}

mpz_class ProdTree(int l, int r)
{
	if (l > r)
		return 1;
	if (l == r)
		return l;
	if (r - l == 1)
		return (mpz_class)r * l;
	int m = (l + r) / 2;
	return ProdTree(l, m) * ProdTree(m + 1, r);
}

mpz_class FactTree(int n)
{
	if (n < 0)
		return 0;
	if (n == 0)
		return 1;
	if (n == 1 || n == 2)
		return n;
	return ProdTree(2, n);
}

mpz_class FactFactor(int n)
{
	if (n < 0)
		return 0;
	if (n == 0)
		return 1;
	if (n == 1 || n == 2)
		return n;
	vector<bool> u(n + 1, false);
	vector<pair<int, int> > p;
	for (int i = 2; i <= n; ++i)
		if (!u[i])
		{
			int k = n / i;
			int c = 0;
			while (k > 0)
			{  
				c += k;
				k /= i;
			}
			p.push_back(make_pair(i, c));                
			int j = 2;
			while (i * j <= n)
			{   
				u[i * j] = true;
				++j;
			}
		}
	mpz_class r = 1;
	for (int i = p.size() - 1; i >= 0; --i)
	{
		mpz_class w;
		mpz_pow_ui(w.get_mpz_t(), mpz_class(p[i].first).get_mpz_t(), p[i].second);
		r *= w;
	}
	return r;
}

mpz_class FactNative(int n)
{
	mpz_class r;
	mpz_fac_ui(r.get_mpz_t(), n);
	return r;
}

int main()
{
	int n;
	unsigned int t;	

	cout << "n = ";
	cin >> n;
	
	t = clock();
	mpz_class fn = FactNaive(n);
	cout << "Naive: " << (clock() - t) * 1000 / CLOCKS_PER_SEC << " ms" << endl;

	t = clock();
	mpz_class ft = FactTree(n);
	cout << "Tree: " << (clock() - t) * 1000 / CLOCKS_PER_SEC << " ms" << endl;

	t = clock();
	mpz_class ff = FactFactor(n);
	cout << "Factor: " << (clock() - t) * 1000 / CLOCKS_PER_SEC << " ms" << endl;

	t = clock();
	mpz_class fz = FactNative(n);
	cout << "Native: " << (clock() - t) * 1000 / CLOCKS_PER_SEC << " ms" << endl;

	cout << "Check: " << (fn == ft && ft == ff && ff == fz ? "ok" : "fail") << endl;

	return 0;
}