# Find Largest Prime Factor

## Recommended Posts

Just a program mainly for fun and the challenge thought I would post what I have so far, feel free to make pointers and question why I did somethings because lord knows this is probably a really really crappy program. lol

All in the hopes of getting better and programming I offer to you my code

```#include <iostream>
#include <time.h>
#include <math.h>
using namespace std;

int isPrime(long long int n);
int power(int base, int pow);

int main()
{
long long int number = 13195, s=0, t=0;
cout << number << endl;
long int greatPrime=0;

//is prime
if(isPrime(number)==1)
cout << endl << number << " is prime." << endl;
else
cout << endl << number << " is composite." << endl;

//code to find largest prime factor coming soon...

return 0;
}

//Test prime using Miller-Rabin test
int isPrime(long long int n)
{
int x=0, a[5]= {2,3,5,7,11};
if(n%2==0)
{
cout << endl << "Composite." << endl;
return 0;
}
long long int s=0, d=(n-1);
srand(time(NULL));
while(d%2==0)
{
d/=2;
s++;
}
cout << "2^" << s << "*" << d << endl;

int dd = (int)d;

for(int cntr=0; cntr<5; cntr++)
{
x=power(a[x], dd)%n;
if(x!=1 || x!=(n-1))
return 0;
else
continue;
}
return 1;
}

int power(int base, int pow)
{
for(;pow >=1; pow--)
{
base*=base;
}
return base;
}```
Edited by Archerzz

##### Share on other sites

What is this, C++?

you bet

##### Share on other sites

Turns out I am really dumb and over complicate things here is the final code that works perfectly lol.

```#include <iostream>
using namespace std;

int main()
{
long long int number;

cout << "Enter number to test: ";
cin >> number;

for(int x=2; x<(number/2); x++)
{
while(number%x==0)
number/=x;
}

cout << '\nLargest Prime: ' << number << '\n';
return 0;
}```
Edited by Archerzz

##### Share on other sites

That's pretty much the slowest way to do it but it's accurate.

##### Share on other sites

True I think someother day I will return to my original, but not now Im tired of primes. The isPrime function wouldn't always return with the correct result.

##### Share on other sites

Hi all..I'm new with c++..can somebody please explain to me what happened in the for loop.

for(int x=2; x<(number/2); x++)

{

while(number%x==0)

number/=x;

}

##### Share on other sites
Hi all..I'm new with c++..can somebody please explain to me what happened in the for loop.

for(int x=2; x<(number/2); x++)

{

while(number%x==0)

number/=x;

}

It's saying that when integer x is = 2 and when number (the variable that was declared) divided by 2 is less than x.. increment x.

which means it'll add 1 to x until x isn't less than number.

##### Share on other sites
It's saying that when integer x is = 2 and when number (the variable that was declared) divided by 2 is less than x.. increment x.

which means it'll add 1 to x until x isn't less than number.

ummm...i know what you are trying to say, it just seems a little confusing, mainly the part about x...it sets that to 2, its not an if

```for(int x=2; x<(number/2); x++)
{
while(number%x==0)
number/=x;
}
```

what is happening is that an integer named x is declared and initialized to 2(this only happens once). then int checks to see if x is less than the variable number divided by 2. If that is true it will run while loop that will set number equal to number divided by x, until the mod (x) number equals 0. it will then add one to x and then check to see if x is less than number divided by 2 again and it will keep going doing this until x is greater than or equal to number divided by 2.

Edited by RimX

##### Share on other sites

Yes exactly, the int variable x is declared once. I was just saying about the whole expression

##### Share on other sites
ummm...i know what you are trying to say, it just seems a little confusing, mainly the part about x...it sets that to 2, its not an if

```for(int x=2; x<(number/2); x++)
{
while(number%x==0)
number/=x;
}
```

what is happening is that an integer named x is declared and initialized to 2(this only happens once). then int checks to see if x is less than the variable number divided by 2. If that is true it will run while loop that will set number equal to number divided by x, until the mod (x) number equals 0. it will then add one to x and then check to see if x is less than number divided by 2 again and it will keep going doing this until x is greater than or equal to number divided by 2.

That all seems right except that it will continue to divide number by x until there is a remainder in the while loop, not until it equals 0.

##### Share on other sites
That all seems right except that it will continue to divide number by x until there is a remainder in the while loop, not until it equals 0.

yea that's what mod is, its the remainder. "mod(x) number" is more of ther math way to write it out.

Edited by RimX