Cornul11 Cornul11 - 3 months ago 25
C Question

Find a better algorithm for prime factors of a number

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
$

Answer

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