Find a better algorithm for prime factors of a number

Question

I was given an assignement to make a program that that takes a positive int and displays its prime factors.

I observed that when giving numbers bigger than 500000, my program takes a lot of time to find the prime factors.

In the end, i failed, because, when given the integer 776621, the program took longer than 10 seconds to count the results. I would like to find out how to optimize my code, so that it would give results faster. Here's my code:

#include <stdio.h>
#include <stdlib.h>

int ft_isprime(int num)
{
    int i;
    int j;

    i = 0;
    j = 2;
    if (num <= 1 && num >= 0)
        return (0);
    if (num >= 2 && num <= 3)
        return (1);
    while (j < num)
    {
        if (num % j == 0)
            return (0);
        j++;
    }
    return (1);
}
int main(int argc, char **argv)
{
    int num;
    int divisor;
    int prime_divisors[30];
    int i;

    i = 0;
    num = 0;
    if (argc == 2)
        num = atoi(argv[1]);
    divisor = num;
    if (argc != 2)
    {
        printf("\n");
        return (0);
    }
    if (num == 1)
    {
        printf("1\n");
        return (0);
    }
    if (ft_isprime(num))
    {
        printf("%d\n", num);
        return (0);
    }
    while (num > 0 && divisor > 0)
    {
        if (ft_isprime(divisor))
        {
            if (num % divisor == 0)
            {
                num = num / divisor;
                prime_divisors[i] = divisor;
                i++;
                continue;
            }
        }
        divisor--;
    }
    while (i > 0)
    {
        if (i == 1)
            printf("%d", prime_divisors[i-1]);
        else
            printf("%d*", prime_divisors[i-1]);
        i--;
    }
    printf("\n");
    return (0);
}

Example of output:

$> ./fprime 225225 | cat -e
3*3*5*5*7*11*13$
$> ./fprime 8333325 | cat -e
3*3*5*5*7*11*13*37$
$> ./fprime 9539 | cat -e
9539$
$> ./fprime 804577 | cat -e
804577$
$> ./fprime 42 | cat -e
2*3*7$
$> ./fprime 1 | cat -e
1$
$> ./fprime | cat -e
$
$> ./fprime 42 21 | cat -e
$

Are you aware that the prime factorization problem is considered to be *hard*? And the whole modern cryptography is relying on this assumption? — Eugene Sh., Aug 25 '16 at 19:41
I'm voting to close this question as off-topic because it's about optimizing working code, which is more suitable at http://codereview.stackexchange.com/ — Daniel Jour, Aug 25 '16 at 19:42
It's not really a question of optimizing your code; the compiler will take care of that for you. You need to optimize is your *thinking*; to think about how to design a better algorithm. You should avoid doing unnecessary computations (obvious, I know). For example, you check every a trial divisor for primality, but is it necessary? Suppose you start with 2 and then proceed with larger numbers. Once you remove all the 2s, could any even number divide what's left? Once you remove all the 3s, could any multiple of 3 be a factor? So do you really care if a trial divisor is prime? — rici, Aug 25 '16 at 20:04
Also, if you're trying potential divisors sequentially from 2 on up, you can stop checking when you reach ceil(sqrt(num)). — Mark Plotnick, Aug 25 '16 at 20:29
what is the upper limit for the input integer `n`? if not too big you can do modified Sieve of Eratosthenes marking all needed primes (up to `sqrt(n)`). If not you can speed up with periodic sieve of first few primes and test only the rest. See [Prime numbers by Eratosthenes quicker sequential than concurrently?](http://stackoverflow.com/a/22477240/2521214) also this [Finding whether a number has P^Q form or not?](http://stackoverflow.com/a/33075747/2521214) might help — Spektre, Aug 26 '16 at 06:40
@MarkPlotnick, yes, this improved the runtime by 2400% when passing the integer 1492002. Thank you. — Cornul11, Aug 26 '16 at 15:56
@DanielJour, i will know in the future, to ask advices about optimizing working code on the link you provided, thank you. — Cornul11, Aug 26 '16 at 15:56

score 1 · Accepted Answer · 2016-08-26T18:27:19.920

Here's an implementation that runs a little faster:

#include <vector>

using namespace std;

bool isPrime(int n) {
  if (n == 1) {
    return false;
  }

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

  return true;
}

vector<int> getPrimeFactors(int n) {
  if (n == 1) {
    return vector<int>();
  } else if (isPrime(n)) {
    return vector<int>(1, n);
  }

  vector<int> primeFactors;
  while(n > 1) {
    // find next factor
    int factor = 2;
    for (factor = 2; factor <= sqrt(n); factor++) {
      if (n % factor == 0) {
        break;
      }
    }

    // remove as many factors as possible
    while (n % factor == 0 && n > 1) {
      n /= factor;
      primeFactors.push_back(factor);
    }

    if (isPrime(n)) {
      primeFactors.push_back(n);
      n = 0;
    }
  }

  return primeFactors;
}

Thank you, the idea with the sqrt improved the runtime by 2400% when passing the integer 1492002. — Cornul11, Aug 26 '16 at 15:54

Find a better algorithm for prime factors of a number

1 Answers1