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!

Immediately

"long long r ... void whosprime(int x)" – Polymer

Why exactly are you using 2 loops? I don't get it... – Haemoid

The 2 loops find all of the primes between 1 and number x. – Immediately

When you've fixed the signature, you're still left with an algorithm that does much more work than necessary. Consider that the lower divisor of x must be prime. You can then search for factors of x / factor. – Zerline

@harold: if factor is the least prime factor of x, then x / factor cannot have a smaller prime factor, so you continue searching at factor, not at 2. – Quirinus

Gir, I'm sure I could have found the solution many places. I'm trying to further develop my programming and critical thinking skills, however, so the solution doesn't help at all. – Immediately

Hope your ints are 64 bits or this might well not compile (or if it did and you ignored the warnings would loop infinitely.) – Atheling

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.

Garwin

Thank you. Could you possibly comment through the code so I can gain perspective on your thought process here? – Immediately

@BobJohn it basically implements what I said in my comment, it searches for the lowest factor z (which must therefore be prime), then continues to factor n / z, and doesn't go any further than sqrt(n) (shouldn't it be a <= instead of < though?) because there won't be any factors there anyway (suppose there is a divisor y > sqrt(n), you would already have found n / y anyway). – Zerline

You are correct: it should be <=, not <. I always get that wrong. Sorry. I'll edit the code. – Garwin

but your code will print duplicate numbers as well. For example, for 24: 2 2 2 3 will be printed. – Lapse

That's correct: 2 * 2 * 2 * 3 = 24. Usually you want to know both the factors and their multiplicity. If you want only the unique factors and don't care about their multiplicity, you can keep track of the previous factor and output a factor only when it differs from the previous one. – Garwin

I don't understand the part At this point z = 13, and z * z = 169, which is larger than 29, so 29 is prime and is the final factor. Could you elaborate? How did you conclude here that 29 is prime? – Shoifet

@Danijel: If n is composite, then it must have at least two factors, so say n = p * q, and to make things concrete, say p < q. Now p must be less than the square root of n, and q must be greater that the square root of n. In this case, since we've already considered all potential factors less than the square root of n (since z * z > 29), there can be no factor less than 29, no p can possibly exist, therefore 29 must be prime. – Garwin

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

Paleogeography

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++)
    {... 
      ...

Akerboom

@BobJohn: probably int and long are the same size in your C++ implementation. Try long long. – Quirinus

Answer 4

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.

Quirinus

With the program as it is, it doesn't print anything. Given relatively small integers it does what it's supposed to. Others have pointed out great alternatives, though. – Immediately

@Bob: Oops, I misread the program -- I thought the inner loop would be for(int z = 2; z <= i; z++), but it's x rather than i. So the program has to do 600 billion modulo operations before it prints 1, my mistake. Will delete. – Quirinus

Thanks for adding this insightful answer to my problem. I know this isn't the best approach, but I'll continue learning :) – Immediately

Nws. As other people have indicated in their answers, you should only ever have to search up as high as either (a) the second-largest prime factor (counting duplicates), or (b) the square root of the largest prime factor, whichever is larger. Counting to 600 billion is always a slow job. – Quirinus

Answer 5

Try below code:

counter = sqrt(n)
i = 2;

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

Breakdown

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.

Gradin

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

Canales

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;

}

Zonda

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

Sacco

its time complexity is "nlog(n)" – Sacco

Consider adding some context around your code, to help other user understand it. It would improve the quality of your answer... – Peatroy

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.

Tver

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

Breakwater

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! ☻

Obregon

I timed your solution for n=123456789012345678. It finished in 1.10 seconds vs 0.21 for @user448810. – Paleogeography

As you might've noticed, UGD's algorithm has the added benefit of not printing out the same prime factor twice. Regardless of whether that was the OP's intention, it's unfair to compare it against an algorithm that doesn't do that. If the speed discrepancy is so high, though, it's probably best to store the factors in an array for further processing, of course. Another thing is whether the condition while (z * z <= n) brings about any time benefit and in my opinion, no. It is only relevant for the very last division and has to be accompanied with the additional if clause after the loop. – Yahairayahata