素因数分解とか

gistfile1.c

void findXY(int m)
{
    int x = (int)sqrt(m),
        y = 0;
    int diff = x * x - y * y - m;

    while(diff != 0){
        if(diff < 0)
            ++x;
        else
            ++y;

        diff = x * x - y * y - m;
    }

    printf("%d, %d", x, y);
}

gistfile2.c

#include <stdio.h>
#include <stdint.h>
#include <math.h>


/**
素数判定
*/
uint8_t isPrime(uint32_t src){
    if(src <= 1) return 0;
    else if(src < 4) return 1;
    else if(!(src % 2)) return 0;
    else if(((src + 1) % 6) && ((src - 1) % 6)) return 0;
  
	int root = (uint32_t)sqrt((double)src) + 1;
	int i;
	for(i = 5; i < root; i += 6)
		if(!((src % i) && ((src) % (i + 2))))
			return 0;

	return 1;
}


/**
m=(x-y)(x+y)を探す
*/
void findXY(uint32_t m, uint32_t *xpy, uint32_t *xmy)
{
    uint32_t x = (int32_t)sqrt((float)m),
             y = 0;
    int32_t  diff = x * x - y * y - m;

    while(diff != 0){
        if(diff < 0)
            ++x;
        else
            ++y;

        diff = x * x - y * y - m;
    }

    *xpy = x + y;
    *xmy = x - y;
}


/**
素因数分解の結果をコンソールに出力
*/
void primeFactorizePrint(uint32_t n)
{
	uint8_t cnt = 0;
    while(!(n & 1)){//偶数ならループ
        ++cnt;
		n /= 2;
    }
	if(cnt == 1)
		printf("2 * ", cnt);
	else if(cnt)
		printf("2^%d * ", cnt);

	if(n == 1){
		printf("%d * ", n);
		return;
	}

    //nで割り続けてたら素数になった
    if(isPrime(n)){
        printf("%d * ", n);
        return;
    }

	uint32_t p, q;
    findXY(n, &p, &q);

    if(p == q){ //x+yとx-yが等しいなら
        printf("(");
		primeFactorizePrint(p);
		printf(")^2 * ");
        return;
    }

	uint8_t isPp, isPq;
    isPp = isPrime(p);
    isPq = isPrime(q);

    if(isPp)
        printf("%d * ", p);      //素数なので出力
    else
        primeFactorizePrint(p); //素数でないからさらに探索

    if(isPq)
        printf("%d * ", q);      //素数なので出力
    else
        primeFactorizePrint(q); //素数でないからさらに探索
}

int main(void)
{
	primeFactorizePrint(1);		//1 *
    printf("\n");
    primeFactorizePrint(2);		//2 * 1 *
    printf("\n");
    primeFactorizePrint(412);	//2^2 * 103 *
    printf("\n");
    primeFactorizePrint(512);	//2^9 * 1 *
    printf("\n");
    primeFactorizePrint(27);	//(3 * )^2 * 3 *
    printf("\n");
    primeFactorizePrint(153);	//17 * (3 * )^2
    printf("\n");
    primeFactorizePrint(14402); //2^1 * 379 * 19 *
    printf("\n");
    primeFactorizePrint(75);	//5 * 3 * 5 *
    printf("\n");

    return 0;
}