Jump to content
Sign in to follow this  
Archerzz

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×