### Finding the largest prime factor from a user input number

Pages: 12
I know this is a pretty simple problem but I've looked over what I've done many times and I just can't see where it's going wrong. The idea is that the user enters a number N when prompted and the program returns the largest prime factor of that number. Any help finding my mistake would be great!

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445`` ``````#include #include #include int main() { std::vector primes; //Initializing variables primes.push_back(2); int test =3; int primes_found = 1; int N; std::cout << "Enter a number N: " << std::endl; //User input the number you want to find std::cin >> N; //Largest prime factor for while (test < N) { // Only want numbers less than N bool is_prime = true; for (int i =0; i < primes.size(); i++) { if (primes[i] > std::sqrt(test)) { //Conditions for being valid as a factor if (N%test == 0) { break; } } if (test%primes[i] ==0) { //Filters out the primes is_prime = false; break; } } if (is_prime) { //Only those test values which are true //make it here primes.push_back(test); primes_found += 1; } test +=2; } std::cout << primes.back() << std::endl; //Print the last prime number in the vector return 0; }``````
Last edited on
How about a different approach? First make a list of all primes in [2..N]. Then iterate over the list in reverse until you find a prime that is a factor for N. Currently you do those simultaneously, and the logic fails somewhere.

Note: primes_found is not really used, and `assert( primes.size() == primes_found )` seems to hold at every step.
I propose a process starting in descending order from the entered number n to find a divisor i of n. Then test if i is a prime number or not. If it is a prime number the process stops. Obviously i is the largest prime divisor of n. If i is not a prime number the descending search will be continued. The following code illustrates such an idea.

 ``12345678910111213141516171819202122232425262728293031323334353637`` ``````#include using namespace std; bool isDivisible(int); bool isPrime(int); int main() { int n; cout << "Enter a number: "; cin >> n; if(n > 0); if( !isDivisible(n) ) cout << "The entered number is prime itself!" << '\n'; return 0; } bool isDivisible( int k ) { for(int i = k / 2; i > 1; i--) if( k % i == 0) { if( isPrime(i) ) { cout << "The largest prime factor of " << k << " is " << i << ".\n"; return true; } } return false; } bool isPrime( int k ) { for(int i = 2; i * i <= k; i++) if(k % i == 0) return false; return true; }``````

Last edited on
Using a sieve:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142`` ``````#include #include #include #include bool prime( std::uintmax_t number, const std::vector& sieve ) { const std::size_t SZ = std::ceil( std::sqrt(number) ) + 1 ; for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] && !(number%i) ) return false ; return true ; } int main() { std::uintmax_t N ; if( std::cout << "N? " && std::cin >> N ) { const std::size_t SZ = std::ceil( std::sqrt(N) ) + 1 ; // generate a prime number sieve upto the square root of N std::vector sieve( SZ, true ) ; for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] ) for( auto j = i*i ; j < SZ ; j += i ) sieve[j] = false ; std::uintmax_t largest_prime_factor = 1 ; // start with 1 because N may be a prime for( std::size_t i = 1 ; i < SZ ; ++i ) if( sieve[i] && N%i == 0 ) { if( prime( N/i, sieve ) ) { largest_prime_factor = N/i ; break ; // N == x*i, x>sqrt(i), and x is a prime } else largest_prime_factor = i ; } std::cout << "largest prime factor of " << N << " is " << largest_prime_factor << '\n' ; } }``````
I think you guys are making this too complex try...

 ``123456789101112131415161718`` ``````#include using namespace std; int main() { long long int number; cout << "Pick your number:"; cin >> number; for(int i=2; i

Something like this, but haven't tested it yet so you can play with it.
Last edited on
I think this is correct been a while since I made one but try something like this maybe
 ``123456789101112131415161718192021`` ``````#include #include const unsigned long long largest_prime_factor( const unsigned long long &number ) { unsigned long long temp = number; if( temp % 2 == 0 ) return( 0 ); for( unsigned long long i = 3uLL; i < static_cast( temp / 2 ); i += 2 ) { std::cout << i << std::endl; if( temp % i == 0 ) temp /= i; } return( temp ); } int main() { unsigned long long number; std::cout << "Please enter a number less than" << std::numeric_limits::max() << ".\n> " << std::flush; std::cin >> number; std::cout << "The largest prime number of " << number << " is " << largest_prime_factor( number ) << std::endl; }``````

This will compile fast it uses that one law forgot the name of it but it is used for finding the largest prime factor.
The idea is simple.
At first fill a vector with prime numbers for example x such that x * x <= N
Then use standard algorith std::find_if

 ``1234`` ``````auto it = std::find_if( v.rbegin(), v.rend(), [=]( int x ) { return ( N % x == 0 ); } ); std::cout << "largest prime factor of " << N << " is " << *it << '\n' ;``````

Last edited on
I believe sieve is not the "right" solution to this problem. What if the user enter 4294967291, or 2147483647 ? The sieve will run for like 30s - 2 minutes

nvm I got it just sieve up to sqrt(n)...
Last edited on
sieve is a lot faster than any other method...Try mine then try the other one where it doesn't divide but checks each number for prime..that will take like 10 hours
@giblit: loop it backward, begin from sqrt(n).

ex: n=100 000 000
loop i from 10 000 downto 2 step -2
if n%i==0 and i is prime => return i
*if no i is returned, then n is prime => return n

the complexity is O(sqrt(n)), which is pretty fast.

meh again I was wrong ~.~

this is the answer without sieve
 ``123456789101112`` ``````unsigned largest_prime_factor(unsigned n) { unsigned lpf = 0; unsigned stop = sqrt(n); for (unsigned i=2; i<=stop; ++i) if (n%i==0) { lpf = i; while (n%i==0) { n/= i; } stop = sqrt(n); } return n==1 ? lpf : n; }``````

http://ideone.com/fuBcC6
Last edited on
Yours takes .002 seconds longer than my method =p for project euler # 3.

I still think it looks best like this
 ``1234567891011121314151617181920`` ``````#include const unsigned short factor( unsigned long long &number ) { auto i( 1uLL ); if( number % 2 == 0 ) number /= 2; while( number > 1 ) { i += 2; if( number % i == 0 ) number /= i; } return( i ); } int main() { auto number( 600851475143uLL ); std::cout << factor( number ) << std::endl; }``````
Last edited on
@giblit: `factor( 2 )` seems to return 1, but surely 2 is the bigger prime? Furthermore, `factor( 9 )` ... best looks don't count everywhere.
 ``12345678910111213141516171819202122232425262728293031323334`` ``````#include int main() { while ( true ) { std::cout << "Enter a non-negative number (0 - exit): "; unsigned long long n = 0; std::cin >> n; if ( !n ) break; unsigned long long tmp = n; unsigned long long prime_factor = 1; if ( n % 2 == 0 ) { prime_factor = 2; do { n /= 2; } while ( n % 2 == 0 ); } for ( unsigned long long i = 3; i <= n; i += 2 ) { if ( n % i == 0 ) { prime_factor = i; do { n /= i; } while ( n % i == 0 ); } } std::cout << tmp << ":\t" << prime_factor << std::endl; } }``````

 ```Enter a non-negative number (0 - exit): 600851475143 600851475143: 6857 Enter a non-negative number (0 - exit):```
Last edited on
@giblit: you need `while` ( number % i == 0 ) number /= i;

my extended, somewhat optimized version:

 ``12345678910111213141516171819202122232425262728293031323334353637383940`` ``````#include #include using std::cout; //if you have C++11 then use uint64_t in cstdint typedef unsigned long long uint64_t; void shrink(uint64_t& n, uint64_t i, uint64_t& lpf, uint64_t& stop) { lpf = i; while (n%i==0) { n/= i; } stop = ceil(sqrt(n)); } uint64_t largest_prime_factor(uint64_t n) { uint64_t lpf = 0; uint64_t stop = ceil(sqrt(n)); //should have ceil() or +1 if (n%2==0) { shrink(n, 2, lpf, stop); } if (n%3==0) { shrink(n, 3, lpf, stop); } for (uint64_t i=7; i<=stop; i+=6) //i ~ 6k+1 { uint64_t j = i-2; //j ~ 6k-1 if (n%j==0) { shrink(n, j, lpf, stop); } if (n%i==0) { shrink(n, i, lpf, stop); } } return n==1 ? lpf : n; } int main() { cout << largest_prime_factor(2147483647) << "\n"; cout << largest_prime_factor(4294967291) << "\n"; cout << largest_prime_factor(4294967294) << "\n"; cout << largest_prime_factor(65536) << "\n"; cout << largest_prime_factor(2*2*2*7*13*19) << "\n"; //cout << largest_prime_factor(2147483647ULL*2147483647ULL) << "\n";//28s //cout << largest_prime_factor(9223372036854775783ULL * 2) << "\n"; //44s //cout << largest_prime_factor(18446744073709551557ULL) << "\n"; //71s }``````

Last edited on
Or one more result

 ```Enter a non-negative number (0 - exit): 6008514751432 6008514751432: 574647547 Enter a non-negative number (0 - exit):```
its supposed to be like 5700 something for 600Billion not 574million =p
for ( unsigned long long i = 3; i <= n; i += 2 )
If n is a very large prime (~10^17) then it will take forever to run...

i should stop at sqrt(n)+1 => maximum loop for 64-bit int is 2^32 ~ 4.3 billions

Or better re-calculate sqrt(n) after dividing n by i(s)
Last edited on
 @giblit its supposed to be like 5700 something for 600Billion not 574million =p

You can check yourself
`std::cout << std::boolalpha << ( 6008514751432ull % 574647547ull == 0 ) << std::endl;`
Last edited on
@edit also I don't think it is 600 billion or million I just glanced at them...
yeah but..574647547 is not a prime I thought we were talking about the largest prime factors not composite factors.

oh you edited the number I thought it was the same as before..you added a 2 to the end sorry.

Last edited on
if to use the maximum value of unsigned long long then the result is

 ```Enter a non-negative number (0 - exit): 18446744073709551615 18446744073709551615: 6700417 Enter a non-negative number (0 - exit):```

The condition in my for loop is invalid. I rewrote it for myself such a way that it would be correct.:) Otherwise the loop can be infinite for some values.
Last edited on
Pages: 12