# Prime factors of a big number

Given a number N, print all the prime factors and their powers. Here N <= 10^18

Examples :

```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. ```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We cannot use Sieve’s implementation for a single large number as it requires proportional space. We first count the number of times 2 is the factor of the given number, then we iterate from 3 to Sqrt(n) to get the number of times a prime number divides a particular number which reduces every time by n/i. We divide our number n (whose prime factorization is to be calculated) by its corresponding smallest prime factor till n becomes 1. And if at the end n>2, it means its a prime number, so we print that particular number.

## C++

 `// CPP program to print prime factors and their ` `// powers. ` `#include ` `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*/`

/div>

## 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

 `>= 1;  ` `        ``\$count``++; ` `    ``} ` ` `  `    ``// if 2 divides it ` `    ``if` `(``\$count``) ` `        ``echo``(2 . ``" "` `. ``\$count` `. ````" "````); ` ` `  `    ``// 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. ` `?> `

Output :

```2 18
5 18
```

Time complexity : O(sqrt(n)).

## tags:

Mathematical prime-factor Mathematical