Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Integer Factorization
2.1.
Method of Wheel Factorization
2.1.1.
Algorithm
2.1.2.
Code
2.2.
Method of Trial Divison
2.2.1.
Algorithm
2.2.2.
Code
2.3.
Method of Precomputed Primes
2.3.1.
Algorithm
2.3.2.
Code
2.4.
Method of Fermat Factorization
2.4.1.
Algorithm
2.4.2.
Code
3.
Frequently Asked Questions
3.1.
Factorization: what is it?
3.2.
What exactly are prime numbers?
3.3.
A Composite Number is what?
3.4.
What is the Eratosthenes Sieve referred to as?
3.5.
What are some popular techniques for determining a positive integer's prime factorization?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

What are Factoring Algorithms?

Author Yashi Agarwal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

As we all know, factorization divides a larger number into the products of several smaller numbers. Every positive number can be factored into the product of various prime numbers, but these products cannot be factored further into positive integers larger than one. The extremely difficult issue of factorizing huge positive integers has led to the creation of numerous cryptographic methods, including the RSA Cryptosystem. There are multiple algorithms available to aid in computing a positive integer's factors.

factoring algorithm

We'll talk about some significant integer factorization algorithms in this blog.

Integer Factorization

We'll talk about a few factoring algorithms now.

Method of Wheel Factorization

This approach is an improvement on the Trial division approach.

Algorithm

In this approach, we shall repeatedly divide n by 2. We do not need to check every other even integer after the number is not divisible by 2. We now only have to look for half the numbers. Then, we proceed by repeatedly dividing n by 3. However, the subsequent division step can discard all multiples of 3 if the value is not divisible by 3. There are only 33.3% of the numbers left for us to verify. We can create a list of primes to check and skip in this fashion.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<ll> WheelFactorization(ll num) {
    vector<ll> divisor;
    for (int a : {2, 3, 5}) {
        while (num % a == 0) {
            factor.push_back(a);
            num /= a;
        }
    }
    static array<int, 8> inc = {4, 2, 4, 2};
    int i = 0;
    for (ll a = 7; a * a <= num; a += inc[i++]) {
        while (num % a == 0) {
            factor.push_back(a);
            num /= a;
        }
        if (i == 8)
            i = 0;
    }
    if (num > 1)
        divisor.push_back(num);
    return divisor;
}
Output

Method of Trial Divison

This is one of the most straightforward procedures for determining a positive integer's prime factorization.

Algorithm

We are given the prime factorization of the positive number n, which we must determine. We continue to divide num by each of its potential divisors, a. The notion that no single prime factor of a composite number can be larger than the square root of num is utilized in this situation.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<ll> TrialDivison(ll num)
{
    vector<ll> divisors;
    for (ll a = 2; a * a <= num; a++)
    {
        while (num % a== 0)
        {
            factors.push_back(a);
            num /= a;
        }
    }
    if (num > 1){
        divisor.push_back(num);
    }
    return divisors;
}
output

Method of Precomputed Primes

This approach improves on the Wheel Factorization approach.

Algorithm

We know that the wheel factorization approach is extended, leaving us with just prime integers to verify. The Sieve of Eratosthenes method is the best way to calculate all the prime integers between 1 and num. I'll therefore use the Sieve of Eratosthenes to precalculate all prime numbers up to sqrt(n).

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<ll> primes;
 
vector<ll> PrecomputedFactors(ll num)
{
    vector<ll> divisors;
    for (ll a : divisors)
    {
        if (a * a > num)
            break;
        while (num % a == 0)
        {
            divisors.push_back(a);
            num /= a;
        }
    }
    if (num > 1)
        divisors.push_back(num);
    return divisors;
}
output

Method of Fermat Factorization

This approach is based on the notion that the difference of the square of two numbers can be expressed as an odd integer.

Algorithm

An odd composite number, num = p * q, can be written as the difference of two squares, num = a - b. a = (p + q)/2 and b = (p - q)/2, respectively. This approach tries to take advantage of the fact by guessing the first square, a2, and then determining whether the remaining portion, b2, equals a2, minus a num is also a square number. If so, we have discovered the factors a - b and a + b for n. This process is more rapid. If the difference between two prime numbers, p, and q, is tiny, this approach operates more quickly. When p and q differ significantly, this method performs very slowly.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll FermatMethod(ll num)
{
    ll a = ceil(sqrt(num));
    ll b = a * a - num;
    ll ba = round(sqrt(b));
    while (ba * ba != b)
    {
        a = a + 1;
        b = a * a - num;
        ba = round(sqrt(b));
    }
    return a - ba;
}
output
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Factorization: what is it?

The process of factorization involves breaking up a larger number into products of several smaller integers.

What exactly are prime numbers?

A prime number can be divided only by one and by itself. Typical prime numbers are 2, 3, 5, 7, 11, 13,17,19 and so on.

A Composite Number is what?

A number with more than two elements is said to be composite. 4, 6, 8, 9, 10, 12, 14, and other popular prime numbers are only a few.

What is the Eratosthenes Sieve referred to as?

The Sieve of Eratosthenes is a technique for identifying prime and composite numbers in a collection of numbers.

What are some popular techniques for determining a positive integer's prime factorization?

The Trial Divison Method, Wheel Factorization Method, Fermat's Factorization Method, and others are frequently used to determine the prime factorization of a positive integer.

Conclusion

In this article, we have discussed what are and different factoring algorithms used for integer factorization. I hope you enjoyed this blog on What are the Factoring Algorithms?

If you want to learn more, check out our articles on Implementing DELETE Method to Delete a User ResourceTechnological Services in Ready APIWhat Is Web2Py?Why To Use Web2py?Postbacks and Internationalization in web2pyThird Party Modules In Web2pyTasks In Web2py, and XML in Web2py.

Also, check out these exciting courses from coding ninjas to expand your knowledge, Coding CourseCode StudioInterview ExperienceGuided PathInterview ProblemsTest SeriesLibrary, and Resources

Happy Coding!

Previous article
What is Square Roots Modulo?
Next article
The Pollard P-1 Algorithm
Live masterclass