-5
\$\begingroup\$

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;
       }

    }
            }



            }
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Mast
    Jan 15, 2017 at 9:08

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 15, 2017 at 9:52
  • \$\begingroup\$ 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. \$\endgroup\$
    – Zeta
    Jan 15, 2017 at 13:02
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ even if i use long int or long long int , the error remains..Can u please tell me how to do it ? \$\endgroup\$
    – Razor1692
    Jan 15, 2017 at 8:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.