Dado un número N, imprime todos los factores primos y sus potencias. Aquí N <= 10^18
Ejemplos:
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.
No podemos usar la implementación de Sieve para un solo número grande, ya que requiere un espacio proporcional. Primero contamos el número de veces que 2 es el factor del número dado, luego iteramos de 3 a Sqrt(n) para obtener el número de veces que un número primo divide un número particular que se reduce cada vez por n/i. Dividimos nuestro número n (cuya factorización prima se va a calcular) por su factor primo más pequeño correspondiente hasta que n se convierte en 1. Y si al final n>2, significa que es un número primo, entonces imprimimos ese número en particular.
C++
// CPP program to print prime factors and their
// powers.
#include <bits/stdc++.h>
using namespace std;
// function to calculate all the prime factors and
// count of every prime factor
void factorize(long long n)
{
int count = 0;
// count the number of times 2 divides
while (!(n % 2)) {
n >>= 1; // equivalent to n=n/2;
count++;
}
// if 2 divides it
if (count)
cout << 2 << " " << count << endl;
// check for all the possible numbers that can
// divide it
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;
}
// if n at the end is a prime number.
if (n > 2)
cout << n << " " << 1 << endl;
}
// driver program to test the above function
int main()
{
long long n = 1000000000000000000;
factorize(n);
return 0;
}
Java
//Java program to print prime
// factors and their powers.
class GFG {
// function to calculate all the
// prime factors and count of
// every prime factor
static void factorize(long n) {
int count = 0;
// count the number of times 2 divides
while (!(n % 2 > 0)) {
// equivalent to n=n/2;
n >>= 1;
count++;
}
// if 2 divides it
if (count > 0) {
System.out.println("2" + " " + count);
}
// check for all the possible
// numbers that can divide it
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);
}
}
// if n at the end is a prime number.
if (n > 2) {
System.out.println(n + " " + "1");
}
}
public static void main(String[] args) {
long n = 1000000000000000000L;
factorize(n);
}
}
/*This code is contributed by 29AjayKumar*/
Python3
# Python3 program to print prime factors # and their powers. import math # Function to calculate all the prime # factors and count of every prime factor def factorize(n): count = 0; # count the number of # times 2 divides while ((n % 2 > 0) == False): # equivalent to n = n / 2; n >>= 1; count += 1; # if 2 divides it if (count > 0): print(2, count); # check for all the possible # numbers that can divide it 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; # if n at the end is a prime number. if (n > 2): print(n, 1); # Driver Code n = 1000000000000000000; factorize(n); # This code is contributed by mits
C#
// C# program to print prime
// factors and their powers.
using System;
public class GFG
{
// function to calculate all the
// prime factors and count of
// every prime factor
static void factorize(long n)
{
int count = 0;
// count the number of times 2 divides
while (! (n % 2 > 0))
{
// equivalent to n=n/2;
n >>= 1;
count++;
}
// if 2 divides it
if (count > 0)
Console.WriteLine("2" + " " +count);
// check for all the possible
// numbers that can divide it
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);
}
// if n at the end is a prime number.
if (n > 2)
Console.WriteLine(n +" " + "1" );
}
// Driver Code
static public void Main ()
{
long n = 1000000000000000000;
factorize(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to print prime
// factors and their powers.
// function to calculate all
// the prime factors and count
// of every prime factor
function factorize($n)
{
$count = 0;
// count the number of
// times 2 divides
while (!($n % 2))
{
// equivalent to n = n / 2;
$n >>= 1;
$count++;
}
// if 2 divides it
if ($count)
echo(2 . " " . $count . "\n");
// check for all the possible
// numbers that can divide it
for ($i = 3; $i <= sqrt($n); $i += 2)
{
$count = 0;
while ($n % $i == 0)
{
$count++;
$n = $n / $i;
}
if ($count)
echo($i . " " . $count);
}
// if n at the end is a prime number.
if ($n > 2)
echo($n . " " . 1);
}
// Driver Code
$n = 1000000000000000000;
factorize($n);
// This code is contributed by Ajit.
?>
Javascript
<script>
// JavaScript program to print prime factors and their
// powers.
// function to calculate all the prime factors and
// count of every prime factor
function factorize(n)
{
var count = 0;
// count the number of times 2 divides
while ((n % 2)==0) {
n = parseInt(n/2) // equivalent to n=n/2;
count++;
}
// if 2 divides it
if (count)
document.write( 2 + " " + count + "<br>");
// check for all the possible numbers that can
// divide it
for (var i = 3; i <= parseInt(Math.sqrt(n)); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = parseInt(n / i);
}
if (count!=0)
document.write( i + " " + count + "<br>");
}
// if n at the end is a prime number.
if (n > 2)
document.write( n + " " + 1 + "<br>");
}
// driver program to test the above function
var n = 1000000000000000000;
factorize(n);
</script>
Producción:
2 18 5 18
Complejidad de tiempo : O (sqrt (N)), ya que estamos usando un bucle para atravesar sqrt (N) veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.