Find Largest Prime Factor

[Archerzz]

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 June 7, 2018 by Archerzz

[d3bruts1d]

What is this, C++?

[Archerzz]

you bet

[Archerzz]

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 June 7, 2018 by Archerzz

[Waco]

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

[Archerzz]

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.

[callister]

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;

}

[MisFiT_]

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.

[RimX]

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 February 26, 2010 by RimX

[MisFiT_]

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

[CheeseMan42]

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.

[RimX]

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 February 27, 2010 by RimX