Prime factorization code

[Crescent13]

I am trying to make a code to find the prime factors of a number in C++, here is what i have so far,

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;
double Abs(double Nbr)
{
if( Nbr >= 0 )
return Nbr;
else
return -Nbr;
}

double SquareRoot(double Nbr)
{
double Number = Nbr / 2;
const double Tolerance = 1.0e-7;

do Number = (Number + Nbr / Number) / 2;
while( Abs(Number * Number - Nbr) > Tolerance);

return Number;
}


int main(int argc, char *argv[])
{
double Number;
cin >> Number;
cout.precision(1);
double Nbr = SquareRoot(Number);
double x;
for (x = Nbr; x <= Nbr && x > 2; x--) {
cout << x << endl;
}
system ("PAUSE");
return 0;
}

I cannot take credit for the algorithim that finds the square root, I got that off the internet. I have done the rest. So far I can only find the numbers that are less than the square root, and I want to find the numbers less than the square root that have no remainders. I think that should get me the prime factors, Any suggestions?

 

[Matthias99]

1) you won't believe this, but there are abs() and sqrt() functions in the C math libraries that do absolute values and square roots. They probably do it a *hell* of a lot faster than that iterative mess you have in your SquareRoot() function.

2) One (extremely naive) algorithm is:

for( int i = 3; i < sqrt( <target number> ); i++ )
{
if( i is prime )
{

for( int j = i; j < sqrt( <target number> ); j++ )
{
if( j is prime )
{
if( j * i == <target number> )
{
add (j,i) to list of prime factors of <target number>;
}
}
}

}
}

A massive improvement first-order improvement would be to precalculate a list of all the primes between 3 and sqrt( <target number> ), and then you just say:

int num1, num2, i, j;

for( i = 0; i < listOfPrimes.size(); i++ )
{
num1 = listOfPrimes[ i ];
j = i+1;
for( num2 = listOfPrimes[j]; num1 * num2 < sqrt( <target number> ); j++ )
{
if( i * j == <target number> )
add (i,j) to list of prime factors of target number;
}
}

There are numerous algorithms for determining if a number is prime; a google search will probably turn up quite a few. One of the simplest is the Sieve of Eristothenes (which can be used to produce lists of prime numbers), so you might start there. You can build a list of primes up to some number x once, and then this algorithm will fairly rapidly tell you the prime factors of any number <= x^2.

 

[bobsmith1492]

Hm, this sounds like a homework problem. We had to make a prime numbers finder in my intro to C programming class....