Prime Factorisation Method Using Sieve O(log n) For Multiple Queries

Prime Factorisation Method Using Sieve O(log n) For Multiple Queries
Prime Factorisation Method Using Sieve O(log n) For Multiple Queries

Introduction

Prime Factorisation Method is the method used to represent any number as the product of all prime factors of a given number. Prime numbers mean numbers with only two factors, one and the number itself. 

For example, numbers such as 2, 3, 5, 7, 11, 13, 15, 17, and so on. All these numbers are not divisible further and have the prime factors, either one or the number itself. 

Consider any number 15, and we have to write its prime factors using the Prime Factorisation Method. We can represent 15 as 3 x 5. Both 3 and 5 are the prime factors. This method of representing 15 as 3 x 5 is called the Prime Factorisation Method

There are different ways of using prime factorization. In this article, you will learn about the Prime Factorisation Method using Sieve O (log n) for multiple queries. But before doing that, first, understand the Sieve of Eratosthenes. Let us get started.

Sieve of Eratosthenes

Sieve of Eratosthenes is a mathematical algorithm that provides the most efficient way to find all the prime numbers smaller than N, where N is less than 10 million.

For example: If N is 15, the output will consist of all the prime numbers less than or equal to 15 and are prime numbers. Therefore, the output is 2, 3, 5, 7, 11, and 13. Similarly, if the input is 30, the output is 2, 3, 5, 7, 11, 13, 17, and 19.

In simple words, the Sieve of Eratosthenes gives a list of prime numbers up to a given number.

How does the Sieve of Eratosthenes Algorithm work?

The algorithm is very simple. Understand it with an example, where N is 20.

234567891011121314151617181920

First of all, we will start with the smallest prime number, i.e., 2. Mark all the numbers from 2 to 20 that are proper multiples of 20. The proper multiples of 2 mean all the numbers that are greater than 2 and are divisible by 2.

234567891011121314151617181920

Clearly, in the list above, after 2, 3 is the number that remains unmarked. Considering 3 as the composite or the prime number, mark all the numbers that are proper multiples of 3.

blog banner 1
234567891011121314151617181920

Considering the next unmarked number, i.e., 5, we will mark all the numbers that are proper multiples of 5.

234567891011121314151617181920

Similarly, we will follow this process of marking the proper multiples of the next unmarked number till the end of the list. All the unmarked numbers in the list are the prime factors of a given number, 20 in this case.

234567891011121314151617181920
234567891011121314151617181920
234567891011121314151617181920
234567891011121314151617181920
234567891011121314151617181920

All the numbers in the last row, which are unmarked and highlighted in yellow are prime factors of a given number. Hence. Output consists of 2, 3, 5, 7, 11, 13, 17, and 19.

Prime Factorisation Method using Sieve O (log n) for multiple queries

Coming to the main topic, we can determine the prime factors of a given number N in 0(sqrt(n)). But 0 (sqrt(n)) times out while answering multiple queries about the prime factorization algorithm. Thus, 0(n) space provides the efficient method of calculating the prime factorization with 0 (log n) as the time complexity for each allowed computation. 

The primary concept behind this method is storing the Smallest Prime Factor (SPF) of numbers. Then, find the prime factors of a given number by dividing the number by the smallest prime number recursively, until the number becomes 1. The Sieve of Eratosthenes algorithm gets used to finding the Smallest Prime Factor.

The below code can get used to calculate the prime factorization.

Pseudo Code for prime factorization assuming SPFs are computed:

PrimeFactors[] // Create a list that stores the result
i = 0  // i is a variable that determines the index of prime factors
//Start a loop that works until number becomes 1
while n != 1 :
    PrimeFactors[i] = SPF[n]
    i++
    n = n / SPF[n]

Below is the above pseudo-code implemented using Python Programming language:

Program to find Prime Factors of a Given Number n in 0 (log n) time while allowing the precomputation.

import math
N = 100001
# Create variable SPF to store smallest prime factor for each number
spf = [0 for a in range(N)]
# Calculating Smallest Prime Factor (SPF) for every number up to MAXN with Time Complexity as O (n log log n)
def sieve():
    spf[1] = 1
    for a in range(2, N):
        # Smallest prime factor for every number is marked to be itself
        spf[a] = a
    # Mark spf for even number as 2
    for a in range(4, N, 2):
        spf[a] = 2
    for a in range(3, math.ceil(math.sqrt(N))):
        # checking if a is prime
        if (spf[a] == a):
            # Mark SPF of all numbers that are divisible by a
            for b in range(a * a, N, a): 
                # Checking if spf[b] is not marked earlier
                if (spf[b] == b):
                    spf[b] = a
# Creating O (log n) function that returns prime factorisation by dividing the number by smallest prime factor (SPF) at each step
def getFactorisation(i):
    ret = list()
    while (I != 1):
        ret.append(spf[i])
        i = i // spf[i]
    return ret
# Driver code to precalculate the Smallest Prime Factor
sieve()
num = 12246
print("prime factorisation for", num, ": ", end = "")
# Calling function getFactorisation
p = getFactorisation(i)
for a in range(len(num)):
	print(p[a], end = " ")

Time Complexity

Using the Sieve of Eratosthenes, the SPF of a given number can be determined in 0 (n log log n). But in the Prime Factorisation Method, we divide the number N by the smallest prime factor repetitively until the number becomes 1. 

Considering the worst-case scenarios, where the smallest prime factor comes out to be two every time. So the total number of division steps becomes log n. So, the time complexity becomes 0 (log n) for the worst-case scenario.

Applications Using Prime Factorisation

Below are the two primary applications of the Algorithm for Prime Factorisation

1. Cryptography

It is a method to protect information. The programmers, who want to create the code consisting of numbers, simultaneously making them not very heavy and getting processed quickly.

2. HCF and LCM 

HCF and LCM can get calculated using the prime factorization method. First of all, the prime factorization of both numbers gets determined, and then HCF and LCM can be determined. 

HCF gets calculated by multiplying the smallest power of all common prime numbers, and LCM gets calculated by multiplying the highest power of all common prime numbers.

Frequently Asked Questions

What is the Big O of Sieve of Eratosthenes?

Sieve of Eratosthenes provides an efficient method to find the prime numbers smaller than N, where N is less than 10 million. Big O of Sieve of Eratosthenes signifies that the Sieve of Eratosthenes algorithm finds all the prime numbers less than N in 0(N log (log N)) time.

What is the time complexity of the Sieve?

The time complexity of the Sieve is 0 (log n) for the worst-case scenario. It can be concluded from the time taken by the Sieve of Eratosthenes algorithm to find all the prime numbers less than N is 0 (n log log n).
The calculation steps consist of dividing the number N every time by the smallest prime number till the number N becomes 1. Considering the worst case of Sieve Prime Factor as two and log n division steps. Thus, in the worst case, time complexity becomes 0 (log n).

How does the Sieve of Eratosthenes work?

Sieve of Eratosthenes is an algorithm that helps to find all the prime numbers less than a number N. The algorithm works by removing the numbers not meeting some mentioned criteria. Hence, the multiples of known prime numbers get eliminated, and the time to find all the prime numbers up to a limit is minimum.

What is a Segmented Sieve?

Segmented Sieve works on the concept of dividing the range 0 to (n-1) in different segments and then finding the prime number in each segment.

What is a sieve in coding?

Sieve refers to the elimination of numbers that do not meet the specified criteria while finding the prime numbers up to a limit.

Is Prime using Sieve?

Prime numbers can get calculated for a range of numbers using the Sieve of Eratosthenes. Sieve of Eratosthenes is a mathematical algorithm, which is very effective in finding the prime numbers up to a number N with a time complexity of 0 (log n).

Key Takeaways

In this article, we explained the prime factorization algorithm using Sieve O (log n). It is a very efficient method of finding the prime factors of a given number in the smallest possible time with a time complexity of 0 (log n). We have also provided the code using Python programming language to implement the prime factorization method

Coding Ninjas is a great learning platform where you can find many similar technical concepts for free.

Whether you are a student or a professional in IT, who wants to learn new technical concepts for a good career, Coding Ninjas is a great platform for you to follow.