Prime factor in reverse order

#include

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

Addendum

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.

StackExchange Code Review Q#56542, answer score: 7