# Prime factorization - C

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

if(isPrime(number)){
return number;
}
return findNextPrime(number);
}

if(isComposite(otherFactor)){
findPrimeFactors(otherFactor, FIRST_PRIME);
}else{
printf("%d ", otherFactor);
}
}else{

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

• Am also accepting prime numbers from this program, which is not required Nov 21, 2016 at 22:01
• What do you intend to accomplish by stating that it took 15 minutes to write the program? Nov 21, 2016 at 22:24
• @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. Nov 21, 2016 at 22:25

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){


• number+=2, why are your sure that next prime is 2 numbers away? Nov 22, 2016 at 17:05