Рубрики

Основные факторы большого числа

Задав число N, выведите все простые множители и их степени. Здесь N <= 10 ^ 18

Примеры :

Input : 250 
Output : 2  1
         5  3
Explanation: The prime factors of 250 are 2
and 5. 2 appears once in the prime factorization 
of and 5 is thrice in it. 

Input : 1000000000000000000
Output : 2  18
         5  18
Explanation: The prime factors of 1000000000000000000
are 2 and 5. The prime factor 2 appears 18 times in 
the prime factorization. 5 appears 18 times. 

Мы не можем использовать реализацию Sieve для одного большого числа, так как оно требует пропорционального пространства. Сначала мы посчитаем, сколько раз 2 является множителем данного числа, а затем итерируем от 3 до Sqrt (n), чтобы узнать, сколько раз простое число делит конкретное число, которое уменьшается каждый раз на n / i. Мы делим наше число n (первичная факторизация которого должна быть рассчитана) на соответствующий ему наименьший простой множитель до тех пор, пока n не станет равным 1. И если в конце n> 2 это означает его простое число, мы печатаем это конкретное число.

C ++

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

using namespace std;

  
// функция для вычисления всех простых факторов и
// подсчет каждого простого множителя

void factorize(long long n)

{

    int count = 0;

  

    // подсчитать количество раз 2 делит

    while (!(n % 2)) {

        n >>= 1; // эквивалентно n = n / 2;

        count++;

    }

  

    // если 2 делит это

    if (count)

        cout << 2 << "  " << count << endl;

  

    // проверяем все возможные числа, которые могут

    // делим это

    for (long long i = 3; i <= sqrt(n); i += 2) {

        count = 0;

        while (n % i == 0) {

            count++;

            n = n / i;

        }

        if (count)

            cout << i << "  " << count << endl;

    }

  

    // если n в конце простое число.

    if (n > 2)

        cout << n << "  " << 1 << endl;

}

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

int main()

{

    long long n = 1000000000000000000;

    factorize(n);

    return 0;

}

Джава

// Java-программа для печати премьер
// факторы и их возможности.

  

class GFG {

  
// функция для расчета всех
// простые факторы и количество
// каждый главный фактор

    static void factorize(long n) {

        int count = 0;

  

        // подсчитать количество раз 2 делит

        while (!(n % 2 > 0)) {

            // эквивалентно n = n / 2;

            n >>= 1;

  

            count++;

        }

  

        // если 2 делит это

        if (count > 0) {

            System.out.println("2" + " " + count);

        }

  

        // проверяем все возможные

        // числа, которые могут разделить его

        for (long i = 3; i <= (long) Math.sqrt(n); i += 2) {

            count = 0;

            while (n % i == 0) {

                count++;

                n = n / i;

            }

            if (count > 0) {

                System.out.println(i + " " + count);

            }

        }

  

        // если n в конце простое число.

        if (n > 2) {

            System.out.println(n + " " + "1");

        }

    }

  

    public static void main(String[] args) {

        long n = 1000000000000000000L;

        factorize(n);

    }

}

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

python3

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

import math

  
# Функция для вычисления всех простых
# факторы и количество каждого простого фактора

def factorize(n):

    count = 0;

  

    # посчитать количество

    # раз 2 делит

    while ((n % 2 > 0) == False): 

          

        # эквивалентно n = n / 2;

        n >>= 1

        count += 1;

  

    # если 2 делит это

    if (count > 0):

        print(2, count);

  

    # проверить все возможные

    # числа, которые могут разделить его

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

        count = 0;

        while (n % i == 0): 

            count += 1;

            n = int(n / i);

        if (count > 0):

            print(i, count);

        i += 2;

  

    # если n в конце - простое число.

    if (n > 2):

        print(n, 1);

  
Код водителя

n = 1000000000000000000;

factorize(n);

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

C #

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

using System;

  

public class GFG

{

  
// функция для расчета всех
// простые факторы и количество
// каждый главный фактор

static void factorize(long n)

{

    int count = 0;

  

    // подсчитать количество раз 2 делит

    while (! (n % 2 > 0)) 

    {

        // эквивалентно n = n / 2;

        n >>= 1; 

          

        count++;

    }

  

    // если 2 делит это

    if (count > 0)

        Console.WriteLine("2" + " " +count);

  

    // проверяем все возможные

    // числа, которые могут разделить его

    for (long i = 3; i <= (long)

         Math.Sqrt(n); i += 2) 

    {

        count = 0;

        while (n % i == 0) {

            count++;

            n = n / i;

        }

        if (count > 0)

            Console.WriteLine(i + " " + count);

    }

  

    // если n в конце простое число.

    if (n > 2)

        Console.WriteLine(n +" " + "1" );

}

  

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

    static public void Main ()

    {

        long n = 1000000000000000000;

        factorize(n);

          

    }

}

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

PHP

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

  
// функция для расчета всех
// основные факторы и счет
// каждого простого фактора

function factorize($n)

{

    $count = 0;

  

    // посчитаем количество

    // раз 2 делит

    while (!($n % 2)) 

    {

        // эквивалентно n = n / 2;

        $n >>= 1; 

        $count++;

    }

  

    // если 2 делит это

    if ($count)

        echo(2 . " " . $count . "\n");

  

    // проверяем все возможные

    // числа, которые могут разделить его

    for ($i = 3; $i <= sqrt($n); $i += 2)

    {

        $count = 0;

        while ($n % $i == 0) 

        {

            $count++;

            $n = $n / $i;

        }

        if ($count)

            echo($i . " " . $count);

    }

  

    // если n в конце простое число.

    if ($n > 2)

        echo($n . " " . 1);

}

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

$n = 1000000000000000000;

factorize($n);

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


Выход :

2 18
5 18

Временная сложность: O (sqrt (n)).

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

Основные факторы большого числа

0.00 (0%) 0 votes