Prime factorization - C

Question

After learning prime factorization today, below is the C code written,

#include<stdio.h>
#include<stdlib.h>
#define FIRST_PRIME 2
typedef enum {false, true}bool;
bool isEvenlyDivide(int compositeNumber, int number){
 return (compositeNumber % number)? false:true;
}
int findOtherFactor(int compositeNumber, int number){
 return compositeNumber / number;
}
bool isPrime(int wholeNumber){
 int factorLimit = wholeNumber / 2;
 for(int isItFactor = 2; isItFactor <= factorLimit; isItFactor++){
 if(isEvenlyDivide(wholeNumber, isItFactor)){
 return false;
 }
 }
 return true;
}
bool isComposite(int wholeNumber){
 return !isPrime(wholeNumber);
}
int findNextPrime(int primeNumber){
 int number = primeNumber+1;
 if(isPrime(number)){
 return number;
 }
 return findNextPrime(number);
}
void findPrimeFactors(int compositeNumber, int primeNumber){
 if(isEvenlyDivide(compositeNumber, primeNumber)){
 printf("%d ", primeNumber);
 int otherFactor = findOtherFactor(compositeNumber, primeNumber);
 if(isComposite(otherFactor)){
 findPrimeFactors(otherFactor, FIRST_PRIME);
 }else{
 printf("%d ", otherFactor);
 }
 }else{
 int nextPrime = findNextPrime(primeNumber);
 findPrimeFactors(compositeNumber, nextPrime);
 }
 return;
}
int main(int argc, char*argv[]){
 int compositeNumber = atoi(argv[1]);
 if(argc == 1){
 printf("usage: \n");
 printf("% ./findPrimeFactors <someCompositeNumber>\n");
 exit(1);
 }
 findPrimeFactors(compositeNumber, FIRST_PRIME);
}

---

for which, below is the compilation and execution(in cygwin),

Personal-PC ~/code_practice/Computing/recursion
$ gcc dummy.c -o findPrimeFactors
Personal-PC ~/code_practice/Computing/recursion
$ ./findPrimeFactors 29
29 1
Personal-PC ~/code_practice/Computing/recursion
$ ./findPrimeFactors 116
2 2 29
Personal-PC ~/code_practice/Computing/recursion
$ ./findPrimeFactors 16
2 2 2 2
Personal-PC ~/code_practice/Computing/recursion
$ ./findPrimeFactors 14
2 7

---

1. Do you think the code is complete from conceptual and implementation aspect?
2. If yes, Can we further make this code, elegant & high perform?
3. If yes, Can I make it a stateless functional program using C?

Note: It took 15 minutes for me to write this program

• overexchange: Am also accepting prime numbers from this program, which is not required
• skiwi: What do you intend to accomplish by stating that it took 15 minutes to write the program?
• overexchange: @skiwi Intention is to know, What would be the maximum time required by a good programmer, to write this program with elegance and efficiency? Because I need to know, where I stand in programming world? by sharing my computer program? Hope I clarified.

Answer 1

doing cond?false:true is very odd to see and very much prone to mistakes in writing or reading. It's better to use negation in the condition:

bool isEvenlyDivide(int compositeNumber, int number){
 return (compositeNumber % number) == 0;
}

You can reduce the number of checks you do by using the knowledge that you only need to check prime factors up to the square root of wholeNumber, all but one prime is odd:

if(isEvenlyDivide(wholeNumber, 2)){
 return false;
}
for(int isItFactor = 3; isItFactor*isItFactor <= wholeNumber; isItFactor+=2)
 if(isEvenlyDivide(wholeNumber, isItFactor)){
 return false;
 }
}

That can also be used for findNextPrime, speaking of recursion isn't the best way to describe looping until you find something instead prefer an explicit loop:

int findNextPrime(int primeNumber){
 int number = primeNumber+1;
 if(isEvenlyDivide(primeNumber, 2)){
 number ++;
 }
 while(!isPrime(number)){
 number+=2;
 }
 return number;
}

When looping over all primes you can make use of the previous primes you have found to skip the non-primes. This can be done using the for example sieve of Eratosthenes.

• overexchange: number+=2, why are your sure that next prime is 2 numbers away?
• ratchet freak: Because all primes except 2 are odd.