factoriasation

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.c
 * Author: Vojta
 *
 * Created on 11. listopadu 2015, 14:08
 */

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

int isPrime(int n) {
    int i, q;
    if (n < 2)
        return 0;
    for (i = 2; 1; ++i) {
        q = n / i;
        if (q < i)
            return 1;
        if (n == q * i)
            return 0;
    }
    return 1;
}

int nextPrime(int n) {
    n++;
    for (; !isPrime(n); ++n)
        ;
    return n;
}

void printFactorisationSimple(int n) {
    int m = 2;
    printf("%d = ", n);
    while (1) {
        if ( n % m == 0) {
            if (n == m)
                printf("%d\n", m);
            else
                printf("%d*", m);
            n /= m;
        } else {
            m = nextPrime(m);
        }
        if (n == 1)
            break;
    }
}

int getPower(int n, int d) {
    int c = 0;
    while (n % d == 0) {
        c++;
        n /= d;
    }
    return c;
}

int ipow(int base, int exp)
{
    int result = 1;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

void printFactorisationAdvanced(int n) {
    int m = 2, x;
    printf("%d = ", n);
    while (1) {
        if ( n % m == 0) {
            x = getPower(n,m);
            if ( n == ipow(m,x))
                printf("%d^%d\n", m, x);
            else
                printf("%d^%d * ", m, x);
            n /= ipow(m,x);
        } else {
            m = nextPrime(m);
        }
        if (n == 1)
            break;
    }
}


int main(int argc, char** argv) {

    int n, i;
    printf("Zadej cele kladne cislo: ");
    scanf ("%d", &n);


    printFactorisationSimple(n);
    printFactorisationAdvanced(n);

    return (EXIT_SUCCESS);
}