Finding prime factors

Question

#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

I'm trying to find the prime factors of the number 600851475143 specified by Problem 3 on Project Euler (it asks for the highest prime factor, but I want to find all of them). However, when I try to run this program I don't get any results. Does it have to do with how long my program is taking for such a large number, or even with the number itself?

Also, what are some more efficient methods to solve this problem, and do you have any tips as to how can I steer towards these more elegant solutions as I'm working a problem out?

As always, thank you!

Answer 1

Your algorithm is wrong; you don't need i. Here's pseudocode for integer factorization by trial division:

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    if n > 1
        output n

I'll leave it to you to translate to C++ with the appropriate integer datatypes.

Edit: Fixed comparison (thanks, Harold) and added discussion for Bob John:

The easiest way to understand this is by an example. Consider the factorization of n = 13195. Initially z = 2, but dividing 13195 by 2 leaves a remainder of 1, so the else clause sets z = 3 and we loop. Now n is not divisible by 3, or by 4, but when z = 5 the remainder when dividing 13195 by 5 is zero, so output 5 and divide 13195 by 5 so n = 2639 and z = 5 is unchanged. Now the new n = 2639 is not divisible by 5 or 6, but is divisible by 7, so output 7 and set n = 2639 / 7 = 377. Now we continue with z = 7, and that leaves a remainder, as does division by 8, and 9, and 10, and 11, and 12, but 377 / 13 = 29 with no remainder, so output 13 and set n = 29. At this point z = 13, and z * z = 169, which is larger than 29, so 29 is prime and is the final factor of 13195, so output 29. The complete factorization is 5 * 7 * 13 * 29 = 13195.

There are better algorithms for factoring integers using trial division, and even more powerful algorithms for factoring integers that use techniques other than trial division, but the algorithm shown above will get you started, and is sufficient for Project Euler #3. When you're ready for more, look here.

Answer 2

A C++ implementation using @user448810's pseudocode:

#include <iostream>
using namespace std;

void factors(long long n) {
    long long z = 2;
    while (z * z <= n) {
        if (n % z == 0) {
            cout << z << endl;
            n /= z;
        } else {
            z++;
        }
    }
    if (n > 1) {
        cout << n << endl;
    }
}

int main(int argc, char *argv[]) {
    long long r = atoll(argv[1]);
    factors(r);
}

// g++ factors.cpp -o factors ; factors 600851475143

Perl implementation with the same algorithm is below.
Runs ~10-15x slower (Perl 0.01 seconds for n=600851475143)

#!/usr/bin/perl
use warnings;
use strict;

sub factors {
    my $n = shift;
    my $z = 2;
    while ($z * $z <= $n) {
        if ( $n % $z ) {
            $z++;
        } else {
            print "$z\n";
            $n /= $z;
        }
    }
    if ( $n > 1 ) {
        print "$n\n"
    }
}

factors(shift);

# factors 600851475143

Answer 3

600851475143 is outside of the range of an int

void whosprime(int x) //<-----fix heere ok?
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {... 
      ...

Answer 4

Try below code:

counter = sqrt(n)
i = 2;

while (i <= counter)
    if (n % i == 0)
        output i
    else
        i++

Answer 5

Edit: I'm wrong (see comments). I would have deleted, but the way in which I'm wrong has helped indicate what specifically in the program takes so long to produce output, so I'll leave it :-)

This program should immediately print 1 (I'm not going to enter a debate whether that's prime or not, it's just what your program does). So if you're seeing nothing then the problem isn't execution speed, there muse be some issue with the way you're running the program.

Answer 6

Here is my code that worked pretty well to find the largest prime factor of any number:

#include <iostream>
using namespace std;

// --> is_prime <--
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // --> nextPrime <--
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }

Keep in mind that if you want to find the largest prime factor of extremely large number, you have to use 'long' variable type instead of 'int' and tweak the algorithm to process faster.

Answer 7

short and clear vesion:

    int main()
    {
        int MAX = 13195;

        for (int i = 2; i <= MAX; i++)
        {
             while (MAX % i == 0)
             {
                  MAX /= i;
                  cout <<  i << ", " << flush;   // display only prime factors
             }
        return 0;
    }

Answer 8

This is one of the easiest and simple-to-understand solutions of your question. It might not be efficient like other solutions provided above but yes for those who are the beginner like me.

int main() {

int num = 0;
cout <<"Enter number\n";
cin >> num;
int fac = 2;  
while (num > 1) {
    if (num % fac == 0) {
        cout << fac<<endl;
        num=num / fac;
    }
    else fac++;
}
return 0;

}

Answer 9

# include <stdio.h>
# include <math.h>
void primeFactors(int n)
{
    while (n%2 == 0)
    {
        printf("%d ", 2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }
   if (n > 2)
        printf ("%d ", n);
}
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}

Answer 10

Simple way :

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll largeFactor(ll n)
{
        ll ma=0;
        for(ll i=2; i*i<=n; i++)
        {
            while(n%i == 0)
            {
                n=n/i;
                ma=i;
            }
        }
        ma = max(ma, n);
        return ma;
}

int main() 
{
    ll n;
    cin>>n;
    cout<<largeFactor(n)<<endl;
    return 0;
}

Implementation using prime sieve ideone.

Answer 11

Since 600851475143 is out of scope for int as well as single long type wont work here hence here to solve we have to define our own type here with the help of typedef. Now the range of ll is some what around 9,223,372,036,854,775,807.

typedef long long int LL

Answer 12

Try this code. Absolutely it's the best and the most efficient:

long long number;
bool isRepetitive;

for (int i = 2; i <= number; i++) {
    isRepetitive = false;
    while (number % i == 0) {
        if(!isRepetitive){
            cout << i << endl;
            isRepetitive = true;
        }
        number /= i;
    }
}

Enjoy! ☻