# Prime factor in reverse order

#include<stdio.h>

int main(){

int numberGiven,num=2,i=0,stack[100] = {0},top=-1;
// get the number from user
printf("Enter the number : ");
scanf("%d",&numberGiven);

while(numberGiven >= num){
// check for prime-ness of number
for(i=num/2;i>1;i--){
if(num%i == 0){
break;
}
}
// prime factors
while(numberGiven%num == 0 && i==1){
stack[++top] = num;
numberGiven /= num;
continue;
}
num++;
}

while(top>=0){
printf("%d\n",stack[top--]);
}
return 0;
}


Any possible code optimization and improvement of time complexity ?

-

There are several functions that I would have factored out to make the code more clear:

bool isFactorOf(int possibleFactor, int number) {
return number % possibleFactor == 0;
}

bool isPrime(int number) {
int i;
int max = ceil(sqrt(num));
for(i = 2; i <= max; ++i) {
if(isFactorOf(i, num)) {
return false;
}
}
return true;
}


Note:

• I reverted the order of testing the factor (because smaller numbers are more likely to be factors)
• the test can end at the sqrt() because if there was a factor bigger than that, there would have been a corresponding factor smaller than that which we would have found earlier in the loop

The stack should be one data structure with checkable size like:

#define MAX_STACK_SIZE 100
typedef struct {
int size;
int data[MAX_STACK_SIZE];
} Stack;

void initialize_stack(Stack *stack) {
stack->size = 0;
}

void push(Stack *stack, int value) {
assert(stack->size < MAX_STACK_SIZE);
stack->size++;
stack->data[stack->size] = value;
}

int pop(Stack *stack) {
assert(stack->size > 0);
return stack->data[stack->size--];
}

bool empty(Stack *stack) {
return stack->size == 0
}


Now the main loop:

At first lets rewrite your solution with the new functions:

while(numberGiven >= num){
// prime factors
while(isFactorOf(num, numberGiven) && isPrime(num)){
push(&stack, num);
numberGiven /= num;
}
num++;
}


I also removed the unnecessary continue (the loop would continue anyway). Using the short-circuit behavior of && already gives an optimization: The primeness is not tested if num is not a factor. Of course it should not be evaluated multiple times so this is more efficient:

while(numberGiven >= num){
if(isFactorOf(num, numberGiven) && isPrime(num)) {
do {
push(&stack, num);
numberGiven /= num;
} while(isFactorOf(num, numberGiven));
}
num++;
}


Now we only do the checks once. The next easy improvement would be to make bigger steps with num as above 2 each prime must be odd (which means step sizes of 2).

The next big speed improvement would come from using a list of precomputed primes (for example by sieving) to avoid the slow primeness test.

The factor finding should go in its own function as well:

Stack primeFactorsOf(int number) {
Stack stack;
initialize_stack(&stack);
int possibleFactor = 2
while(number >= possibleFactor){
if(isFactorOf(possibleFactor, number) && isPrime(possibleFactor)) {
do {
push(&stack, possibleFactor);
number /= possibleFactor;
} while(isFactorOf(possibleFactor, number));
}
possibleFactor++;
}
return stack;
}


Which leaves your main function as:

int main() {
int givenNumber;
Stack factorStack;
initialize_stack(&factorStack);
printf("Enter the number : ");
scanf("%d",&givenNumber);
factorStack = primeFactorsOf(givenNumber);
while(!empty(&factorStack)){
printf("%d\n", pop(&factorStack));
}
return 0;
}


After thinking a bit more about the algorithm I realized that you can completely remove the primeness check because you test from the lowest to the highest factor. Thus you will always find prime factors before you can find the composite factors because they are composed of these (smaller) prime factors. Leaving out the rather slow primeness check should give you another significant performance boost.

-

I found 2 redundancies here, all of them are meaningless:

1. You don't need check i == 0 at second while loop
2. The continue statement is unnecessary because it is reached the end of that while loop

And you should refer to the prime number checking algorithm Sieve of Atkin. It is considered the fastest one for this work.

-
I suppose by need check i==0 at second while loop you mean && i==1){ which is actually needed because it signifies the result of the primeness check (if i==1 the loop ended because the number is prime and no factor has been found, else i!=1). – Nobody Jul 9 '14 at 13:35
I understand. I cannot explain why for now, but when remove that condition checking, your code still work well. – Dai Nguyen-Van Jul 10 '14 at 8:28
The reason is, that the primeness check is not needed. When you check the factors from lowest to highest then you cannot find composite factors because they are built from prime factors which you removed earlier. I added this to my answer. (See also point 2 of gnasher's second answer) – Nobody Jul 10 '14 at 8:50

To speed this algorithm up, the problem is not with the way that the code is written, the problem is with the mathematical algorithm that you are using. Here's what you need to think about and incorporate in your algorithm:

1. When you try to find factors of a number $x$, there is no point in dividing it by all numbers from 2 to $x-1$, or by all numbers from 2 to $\frac{x}{2}$. If you find a way to write $x$ as the product of two numbers $x = a * b$, can you figure out how large the smaller of the numbers a and b can be at most? If a is the smaller number, and $a*b = x$, then $a*a \le x$. Therefore $a$ is at most ... . So if you don't find a factor $f \le ...$ then you can stop looking because $x$ must be a prime number.

2. There is no need to check that the factors you are looking for are prime numbers. If you found that $x$ has no factors $< f$, and $x$ is divisible by $f$, it is impossible that $f$ is not a prime number. However, you shouldn't just believe this but figure out why that is so. (For example, if $x$ is divisible by 35, what would the algorithm do before you check divisibility by 35?)

3. That said, dividing by numbers that are not prime numbers can never succeed, so it is wasteful and should be avoided if you can do it cheaply. Now ask yourself: How many even prime numbers are there? There's only one. So there is no point dividing by any possible factors that are even except that one even prime number. It's just that you don't avoiding division by an even number $f$ by checking that $f$ is even, you avoid it by never making even numbers $f$ part of your algorithm at all.

4. For extra points, how many prime numbers are divisible by 3? Again, there is only one. Can you find a very cheap way to avoid dividing by any multiples of 3 except the number 3 itself? That can save another one-third of the total work.

-

It took me a while to figure out what your code actually does, because what it does is quite unexpected.

This loop

   for(i=num/2;i>1;i--){
if(num%i == 0){
break;
}
}


tries to find out if num is a prime number, by checking if it is divisible by any number num/2 >= i >= 2 in reverse order. If num is even it finds that num is divisible by (num/2) immediately. In all other cases, the largest divisor of num is at most num/3, so you perform at least num/2 - num/3 = num/6 divisions. That's when num is composite. If num is prime, you do num/2 divisions.

If numberGiven is a prime number, then num will have all values from 2 to numberGiven - 1. There are about (numberGiven) values for num, and on average they are about (numberGiven/2) in size. (numberGiven/2) of the values of num are odd. The odd ones will be tested for being primes, each taking at least num/6 divisions. Since you are testing (numberGiven/2) odd numbers num, with an average size of (numberGiven/2), you take at least (numberGiven/2) * (numberGiven/2) / 6 = numberGiven2 / 24 divisions.

I'd try the algorithm with a prime number around a million and measure the time. A reasonably clever algorithm will find all prime factors with no more than $\frac{\sqrt{n}}{2}$ divisions. If $n$ is around a million, that's 500 divisions, while yours needs more than 42 billion, so expect it to run for a few minutes at least.

-