Finding prime factors of a number

[PirateCat]

Trying to find the prime factors of a number, I am having issues though with the returning of true and false.

For example:
When I enter the number 10 it returns false which is correct.
If I enter the number 100 it returns as false which is incorrect, it should return as true.

bool is_prime(long n) {

  if(n < 2) {
	return false;
  }
  
  for(int i = 2; i <= sqrt(n); i++) {
    if ((n % i) == 0) {
	return false;
    }
  }
  
  return true;
}

Thanks in advance for the help!

[cire]

100 is not a prime number, so returning false would be correct.

[Mantorr22]

You can't do i <= sqrt(n), because 100 is divisable by 10 and as a result the function returns false.

That reminds me of how to find prime numbers long ago, I might forget the way to do it.

[cire]

Again, 100 is not a prime number. Returning false is the correct thing to do.

[PirateCat]

I am trying to find the prime factors of a given number..not if the number is prime or not.

[cire]

I am trying to find the prime factors of a given number..not if the number is prime or not.

Then you've named your function incorrectly and you're going about things the wrong way.

[integralfx]

Something like this?

#include <iostream>

bool is_prime(long n) 
{
    if(n < 2) {
        return false;
    }
      
    for(long i = 2; i * i <= n; i++) {
        if ((n % i) == 0) {
            return false;
        }
    }
      
    return true;
}

int main()
{
    const long num{ 100 };
    
    std::cout << "prime factors of " << num << " = { ";
    for(int i = 0; i <= num; i++) {
        if(is_prime(i) && num % i == 0)
            std::cout << i << ' ';
    }
    std::cout << "}\n";
}

prime factors of 100 = { 2 5 }

For extremely large numbers I'd recommend you use a sieve like the Sieve of Eratosthenes, storing the prime numbers in a vector, then use the same logic as above.

[lastchance]

Can be made slightly more efficient (on average), reducing the search by stripping out prime factors as you find them.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

//============================

int smallestFactor( int n, int start = 2)        // returns smallest factor of n (which must be prime unless n=1)
{                                          
   int test = start;
   int maxTest = sqrt( n );

   while ( test <= maxTest ) 
   {
      if ( n % test == 0 ) return test;
      test++;
   }
   return n;                                     // default if n is either prime or n = 1
}

//============================

vector<int> factorise( int n )                   // factorise n ( > 1 ) into prime factors in ascending order
{
   vector<int> factorList;

   int p = 2;
   while ( n != 1 )
   {
      p = smallestFactor( n, p );
      factorList.push_back( p );
      n /= p;                                    // make more efficient by stripping factor before resuming search
   }
   return factorList;
}

//============================

void writeFactors( int n, vector<int> factors )            // writes out (pre-)computed factors of a number
{
   cout << "Prime factorisation: " << factors[0];
   for ( int i = 1; i < factors.size(); i++ ) cout << " x " << factors[i];
   cout << endl;

   int current = factors[0];
   cout << "Distinct factors: " << current;
   for ( int i = 1; i < factors.size(); i++ )
   {
       if ( factors[i] != current ) cout << ", " << factors[i];
       current = factors[i];
   }
   cout << endl;
}

//============================

int main()
{
   int n;
   cout << "Input n: ";
   cin >> n;

   vector<int> factors = factorise( n );
   writeFactors( n, factors );
}

Input n: 12345678
Prime factorisation: 2 x 3 x 3 x 47 x 14593
Distinct factors: 2, 3, 47, 14593

And where this thread started ...

Input n: 100
Prime factorisation: 2 x 2 x 5 x 5
Distinct factors: 2, 5

[dhayden]

When I enter the number 10 it returns false which is correct.
If I enter the number 100 it returns as false which is incorrect, it should return as true.

Both 10 and 100 correctly return false when passed to your is_prime() function.

I am trying to find the prime factors of a given number..not if the number is prime or not.

is_prime() just tells whether a number is or is not prime. Please post your code that finds factors.

Oh one other thing. You don't want to call sqrt(n) each time through the loop, so it will be much faster to do this:

bool is_prime(long n) {

  if(n < 2) {
        return false;
  }

  int limit = sqrt(n);
  for(int i = 2; i <= limit; i++) {
    if ((n % i) == 0) {
        return false;
    }
  }

  return true;
}

[48T7M4Gy]

Try this. Only gets the unique prime factors, not multiples of them
eg number = 63 -> 3 and 7, but 63 = 3x3X7 which is an additional embellishment to the program.
(Can also be speeded up dramatically by reducing the limits.)

#include <iostream>
#include <cmath>

int* primeList( const int aLimit)
{
    int* sieve = new int[aLimit];
    int sqrt_limit = sqrt( aLimit);
    
    for ( int i = 2; i <= sqrt_limit; i++)
        for (int j = i * i; j < aLimit; j += i)
            sieve[j] = 1;
    sieve[aLimit] = -1; // terminator
    
    return sieve;
}

int main()
{
    int number = 0;
    
    std::cout << "Enter number: ";
    std::cin >> number;
    
    int* list = primeList( number );
    
    for (int i = 2; i < number; i++)
    {
        if( list[i] != 1 )
        {
            if(number % i == 0)
               std::cout << i << ' ';
        }
    }
    std::cout << '\n';
    
    return 0;
}

Enter number: 9699690
2 3 5 7 11 13 17 19 
Program ended with exit code: 0