C++

Forum

 
Finding the largest prime factor from a user input number

Pages: 12
ben353 (4)
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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include <iostream>
#include <vector>
#include <cmath>


int main() {

   std::vector<int> 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
keskiverto (10362)
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.
condor (271)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>

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
JLBorges (13770)
Using a sieve:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <cstdint>
#include <iostream>
#include <cmath>
#include <vector>
 
bool prime( std::uintmax_t number, const std::vector<bool>& 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<bool> 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' ;
    }
}
Manga (1030)
I think you guys are making this too complex try...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
using namespace std;

int main() {
long long int number;
cout << "Pick your number:";
cin >> number;

for(int i=2; i<number; i++) {
  if(number%i == 0) {
    number = number/i;
    i=1;
  }
}
cout << endl << number << endl;

return 0;
}


Something like this, but haven't tested it yet so you can play with it.
Last edited on
giblit (3750)
I think this is correct been a while since I made one but try something like this maybe
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <iostream>
#include <limits>

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<unsigned long long>( 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<unsigned long long>::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.
vlad from moscow (6539)
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

1
2
3
4
 
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
tntxtnt (211)
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
giblit (3750)
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
tntxtnt (211)
@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 
1
2
3
4
5
6
7
8
9
10
11
12
 
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
giblit (3750)
Yours takes .002 seconds longer than my method =p for project euler # 3.

I still think it looks best like this
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>

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
keskiverto (10362)
@giblit: factor( 2 ) seems to return 1, but surely 2 is the bigger prime? Furthermore, factor( 9 ) ... best looks don't count everywhere.
vlad from moscow (6539)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#include <iostream>

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
tntxtnt (211)
@giblit: you need while ( number % i == 0 ) number /= i;

my extended, somewhat optimized version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <iostream>
#include <cmath>
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
vlad from moscow (6539)
Or one more result

Enter a non-negative number (0 - exit): 6008514751432
6008514751432:  574647547
Enter a non-negative number (0 - exit):
giblit (3750)
its supposed to be like 5700 something for 600Billion not 574million =p
tntxtnt (211)
@vlad:
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
vlad from moscow (6539)
@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
giblit (3750)
@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
vlad from moscow (6539)
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