Decomposing a number into primes

Question

I have written the following code to decompose a number into primes. The problem is that it takes so much time and I have no idea why.

#include <stdio.h>
#include <stdlib.h>
int prime (int n){int j=2; 
if (n==2) return 1;
while(j<(n/2)){ 
if(n%j==0) { return 0;}
j=j+1;
}return 1;}

int expotent (int n,int p){int j=0;
while((n%p)==0){
j=j+1;
p=p*p;
}
return j;
}

int main(int argc, char *argv[]) {int h=0,n=1,k=1,t=0 ;
scanf("%d",&n);
int j=n;
while(k!=n){
if(expotent(n,j)!=0 & prime(j)==1)
{
    if(t==0) {t=1; printf("%d^%d",j,expotent(n,j));
for( h<expotent(n,j); h++;){k=k*j;} 
    }
else {
printf("*%d^%d",j,expotent(n,j));
for( h<expotent(n,j); h++;){k=k*j;}}
}
j=j-1;
}
return 0;}

Answer 1

Before you can hope to understand what the code does and why it performs badly, you first have to be able to read it easily. For your benefit and for the benefit of other reviewers, here is your code, with no changes other than whitespace:

#include <stdio.h>
#include <stdlib.h>

int prime(int n) {
    int j = 2;
    if (n == 2) return 1;
    while (j < (n/2)) { 
        if (n % j == 0) {
            return 0;
        }
        j = j + 1;
    }
    return 1;
}

int expotent(int n, int p){
    int j = 0;
    while ((n % p) == 0) {
        j = j + 1;
        p = p * p;
    }
    return j;
}

int main(int argc, char *argv[]) {
    int h = 0, n = 1, k = 1, t = 0;
    scanf("%d", &n);
    int j = n;
    while (k != n) {
        if (expotent(n, j) != 0 & prime(j) == 1) {
            if (t == 0) {
                t = 1;
                printf("%d^%d", j, expotent(n,j));
                for (h < expotent(n,j); h++; ) {
                    k = k * j;
                } 
            } else {
                printf("*%d^%d", j, expotent(n,j));
                for (h < expotent(n,j); h++; ) {
                    k = k * j;
                }
            }
        }
        j = j - 1;
    }
    return 0;
}

Now you can see what the branching and looping structure looks like!