Cornul11 - 1 year ago 123

C 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

$

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**