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
\$
``````

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