Euler’s Factorization method in C++
By Arpit JainHi guys, today we will learn about Euler’s Factorization Method in C++.
As the name suggests, Euler’s Factorization method is a factorizing technique earlier proposed by Marin Mersenne but later put forward by Euler.
In this technique, the number is expressed in two quadratic forms.
Let us assume the number to be N, and hence, we will find the value of 4 variables A, B, C, D such that N = A2 + B2 and N= C2 + D2 and no two variables are equal.
If we can find such 4 variables then only this method applies to it.
Before, we start with this topic, I would like to tell you that indeed the topic is completely mathematical therefore we will be performing various mathematical operations.
Algorithm: Euler’s Factorization method
Now let’s move to the algorithm.
Because it is an equation, we can write it as
N = A2+ B2= C2+ D2
=> A2 – C2= D2 – B2
=> (A-C)(A+C)= (D-B)(D+B) ………………………….(1)
Now, we will be using the GCD, which is the greatest common divisor. You can learn more about GCD by visiting this website.
Next, we will be assuming another variable K which is equal to the GCD of A-C and D – B.
thus,
A-C = K * L ………………………….(2)
=> L= (A-C)/K;
and D – B = K * M ……………………………(3)
=> M=(D-B)/K where GCD(L, M) is 1.
After substituting the equation (2) and (3) in the equation (1), we get
K * L * (A + C) = K * M * (D + B)
=> M/L= (A+C)/(D+B)
Once we are done with this, we will be assuming another variable H which is equal to GCD of A+C and D+B
therefore,
A + C = M * H ……………………………(4)
D + B = L * H ……………………………..(5)
Now,
(K2 + H2 ) ( L2 + M2 )= {(KL)2+ (KM)2+ (HL)2+ (HM)2}
= [(A – C)2+ (D – B)2+ (B+D)2+ (A + C)2]
= 2A2+ 2B2+ 2C2+2D2
= 4N
Therefore, N= 1/4(K2 + H2 ) ( L2 + M2 )
C++ Code For Euler’s Factorization
Let’s move to the code which can find the factors of a number using Euler’s Factorization Method.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,l,k,h;
float a,b,c,d;
cin>>n;
for(int i=0;i<n;i++)
{
b=i;
a=sqrt(n-(i*i));
if(a==(int)a)
break;
}
for(int i=0;i<n;i++)
{
if(b!=i)
{
d=i;
c=sqrt(n-(i*i));
if(c==(int)c)
break;
}
}
int A=a-c;
int B=a+c;
int C=d-b;
int D=b+d;
k=__gcd(A,C);
h=__gcd(B,D);
l=(a-c)/k;
m=(d-b)/k;
cout<<"a="<<a<<"\tb="<<b<<"\tc="<<c<<"\td="<<d<<endl<<"k="<<k<<"\th="<<h<<"\tl="<<l<<"\tm="<<m;
if(k%2==0)
{
k=k/2;
h=h/2;
}
else
{
l=l/2;
m=m/2;
}
cout<<endl<<"factors are\t"<<(k*k)+(h*h)<<" "<<(l*l)+(m*m);
}
So, this is the code in which I have declared 5 integer type variables i.e. n,k,h,l,m.
In addition, I have declared 4 floating type variables i.e. a,b,c,d.
Also, I used float type because I am using the equation a=sqrt(n-(i*i)) which can return a decimal number. However, if I use an integer type then it will result in the wrong answer.
In this program, we will be finding factors of number N which satisfies the condition
N = a2+ b2= c2+ d2.
The first loop is used to find the values of a and b.
On the other hand, the second loop will find the values of c and d.
Initially, we declared a,b,c,d as float type but GCD works only on integer types. That is why we need to declare another variable A, B, C, D.
After that, we will be computing the values of a-c, d-b, a+c, b+d.
Latterly, we will be calculating the GCD of a-c, d-b, and similarly, we will be calculating the GCD of a+c, d+b.
Finally, we are calculating the factors of N i.e. (k/2)2 +(h/2)2 and l2+ m2
or (l/2)2 +(m/2)2 and h2+ k2.
To illustrate, let us take an example,
input:
1000009
Output will be:
a=1000 b=3 c=972 d=235 k=4 h=34 l=7 m=58 factors are 293 3413
To conclude with this topic, I would suggest you to practice this program without seeing the code.
Leave a Reply