A Simple Windows Application for Factorizing Integers

So, I spend so much time working and doing mathematics and walking the dogs that I don’t always spend much time on programming. But, over the last year, I have realized that everything that I need to make windows applications is already on my computer. I don’t need any fancy software: just a text editing program, and an open source compiler to compile from the command line.
So my first code that I am posting here is a C++ application for factorizing integers. It just runs in a window with no fancy GUI. But it factorizes numbers very nicely.

The link for the downloadable exe file is below the code.

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <string>
//  #include <NTL/ZZ.h>  get this number theory stuff eventually

bool primep (int64_t N);

int main()
{
using namespace std;
std::string another ="N";
do
{
int64_t N;
int64_t divisorlist[1000];
int64_t primedivisorlist[100][3];
int64_t sumofdivisors =0;
int64_t phi=1;
int counter (1);
bool squarep (false);
cout<< "This application factors integers of up to seventeen digits."<<endl;
cout << "Enter an integer to be factored: " <<endl;
cin>>N;
cin.ignore(32767, '\n');

for (int m=1; m<= floor(sqrt(N));m++ )
{
if (N%m == 0)
{divisorlist[counter]=m;
counter++;}
}

for(int m=counter-1;m> 0;m--)
{
int64_t quotient = N/divisorlist[m];
if (divisorlist[m] != quotient)
{divisorlist[counter]=quotient;
counter++;
}}
// now extract primes
int bar=1;
for(int m =2; m<=counter-1;m++)
{
if (primep(divisorlist[m]))
{primedivisorlist[bar][1]=divisorlist[m];
bar++;}
}
// now find powers of primes

for (int m=1; m<=bar-1; m++)
{
int power=1;
int64_t x = round(pow(primedivisorlist[m][1], power));

while (N % x ==0
&& x<=N)
{
power++;
x = round(pow(primedivisorlist[m][1], power));
}
primedivisorlist[m][2]=power-1;
}
cout<<N<<" = ";
for(int m =1; m<=bar-1;m++)

{
cout<<primedivisorlist[m][1];
if (primedivisorlist[m][2]>1 )
cout<< "^"<< primedivisorlist[m][2];
if (m<bar-1) cout<<"*";
phi=phi*round(pow(primedivisorlist[m][1], (primedivisorlist[m][2]-1)))*(primedivisorlist[m][1]-1);
}
cout<<endl;

cout<< "Number of divisors: "<<counter-1<<endl;
cout<<"The divisors are: "<<endl;
for(int m =1; m<=counter-1;m++)
{
cout<<divisorlist[m]<<" ";
sumofdivisors = sumofdivisors+divisorlist[m];
}
cout<<endl;
cout<<"The sum of the aliquot divisors of "<<N<<" is "<<sumofdivisors-N<<". Hence, this number is ";
if (sumofdivisors >(2*N)) {cout<<"abundant. "<<endl;}
else if (sumofdivisors<(2*N)){cout<<"deficient. "<<endl;}
else {cout<<"perfect. "<<endl;}

cout<<"Phi, the number of integers less than and relatively prime to "<<N<<" is "<<phi<<endl;
cout<<N<<" is ";
if (primep (N))
cout<<" ";
else cout<<"not ";
cout<<"prime."<<endl;
squarep = (counter-1)%2;
cout<<N<<" is ";
if (squarep)
cout<<" ";
else cout<<"not ";
cout<<"a perfect square."<<endl;
cout<<"Another number? ";

std::getline(std::cin, another);
}
while ((another == "yes") || (another == "y"));

return 0;
}

bool primep (int64_t N)

//returns t if N is prime
{
for (int m=2; m<= floor(sqrt (N)); m++)
{
if (N%m ==0) return false;
}
return 1;
}

The code is very simple and self-explanatory.  It is not the most efficient and beautiful way to factorize a number, but it works well enough within the realm of integers that can be easily handled by the base C++ variable types.

Here is the link for the exe file:

Factorizer

Leave a Reply