# Finding the largest prime factor of a 12 digit number [closed]

I created this using C++ and this gives the largest prime factor of a number.But my problem is if I try to find the largest prime factor of a very large number (12 digit number) it gives an error or it doesn't give an answer. I'm new to programming so please be kind enough to help :)

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
int number;
cout << " Enter the number \t " ;
cin >> number;

for( int counter = number ; counter >1 ; counter --){

int test = number%counter;
int rem;

if( test == 0){
for(int i =2 ; i <= sqrt(counter) ; i++){
rem= counter%i;
if(rem == 0)
break;
}

if( rem != 0){
cout << counter << " IS THE LARGEST PRIME FACTOR OF "<< number <<endl;
break;
}

}
}

}

## closed as off-topic by Mast, t3chb0t, forsvarir, Graipher, DenisJan 15 '17 at 15:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Mast, t3chb0t, forsvarir, Graipher, Denis
If this question can be reworded to fit the rules in the help center, please edit the question.

• Welcome to Code Review! This question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. – Mast Jan 15 '17 at 9:08

In number theory, always think math before you think code.

In your code, you loop over numbers from N to 2 and check whether it is a factor and if it is, whether it is a prime. The problem with this approach should be very clear. In the worst case, you have to loop over $10^{12}$ numbers and if the number has a lot of factors you have to check primality many times.

To fix this, you can directly do a prime factorisation of the number instead by cancelling off primes at each stage. This way, every factor you find is guaranteed to be prime (so that you don't need additional primality checking) and you can stop at sqrt(n) because whatever you are left with is guaranteed to be prime.

long long largestprime(long long N) {
long long prime = 0;
for (long long i=2; i*i <= N; ++i) {
if (N%i == 0) {
// Found a new and larger prime
prime = i;

// Now cancel it off from N
while (N%i == 0) N /= i;
}
}

if (N > 1) {
// We crossed sqrt N and have a large prime left
prime = N;
}
return prime;
}

This would be $\mathcal{O}(\sqrt N)$ and run fast and correctly.

• You can replace the while loop with a do {} while because the condition will be true at least once. This reduces the number of modulo operations needed by 1. Or you can merge the while body into the condition, yielding while ((N /= i) % i == 0);, if that fits your style, though I find that less readable. – Ratatwisker Jan 15 '17 at 9:52
• Also, you can do a special case of i = 2 before the loop, and then use i = 3; i*i <= N; i += 2. Doesn't change the asymptotic complexity, since $\mathcal O(\sqrt(N))$ is equivalent to $\mathcal O\left(\frac{\sqrt(N)}{2}\right)$ by definition, but still lets you skip every second number. – Zeta Jan 15 '17 at 13:02

A 12 digit number is a large number and it would not fit in a data type int, try using long int or even long long int to store the largest prime factor.

• even if i use long int or long long int , the error remains..Can u please tell me how to do it ? – Razor1692 Jan 15 '17 at 8:02