Project Euler #108 (Diophantine reciprocals I)

문제는 https://projecteuler.net/problem=108

x = n + t가 되는 t를 놓고 풀면

y = n + n*n/t가 되고, 여기서 t는 n*n의 소인수가 된다.

이를 이용하여 가능한 t를 n*n 소인수 set에서 iteration시켜 x, y를 유도하고

t가 <=n범위 안에 있을 때 count 시킨다. 그 이유는 x<=y로 놓고 식을 풀면 x <= 2*n이 나오기 때문에 t <= n을 만족해야 한다.

아래는 코드이다. 아직 110번은 못풀었다.

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

#define P 5000
#define ECOUNT 1000
#define LAST 1260

int prime[P];
struct factor {
	int *pcount;
	int size;
};

bool is_prime(int n) {
	int i, sqrtn = sqrt(n);
	for (i = 0; prime[i] <= sqrtn && i < P; i++) {
		if (n % prime[i] == 0)
			return false;
	}
	return true;
}

void init_primes() {
	int idx = 1, n = 3;
	prime[0] = 2;
	while (idx < P) {
		if (is_prime(n)) prime[idx++] = n;
		n += 2;
	}
}

factor* init_factor() {
	factor *f = (factor*)malloc(sizeof(factor));
	int i;
	f->pcount = NULL;
	f->size = 0;
	return f;
}

factor* factor_deep_copy(factor *f) {
	factor *r = (factor*)malloc(sizeof(factor));
	int i;
	r->pcount = (int*)malloc(sizeof(int)*f->size);
	for (i = 0; i < f->size; i++) {
		r->pcount[i] = f->pcount[i];
	}
	r->size = f->size;
	return r;
}

factor* factorize(int n) {
	int i, j, fsize = 0, sqrtn = sqrt(n);
	int pcount[P];

	factor *f = init_factor();
	for (i = 0; prime[i] <= sqrtn; i++) {
		pcount[i] = 0;
		while (n%prime[i] == 0) {
			pcount[i]++;
			n /= prime[i];
			fsize = i + 1;
		}
	}
	if (n > 1) f->size = -1;
	else {
		f->pcount = (int*)malloc(sizeof(int)*fsize);
		for (j = 0; j < fsize; j++) f->pcount[j] = pcount[j];
		f->size = fsize;
	}
	return f;
}

void factor_square(factor *f) {
	int i;
	for (i = 0; i < f->size; i++) {
		f->pcount[i] *= 2;
	}
}

bool is_factor_empty(factor *f) {
	int i;
	if (f->size == 0) return true;
	for (i = 0; i < f->size; i++) {
		if (f->pcount[i] > 0) return false;
	}
	return true;
}

int factor_to_int(factor *f) {
	int n = 1, i, j;
	for (i = 0; i < f->size; i++) {
		for (j = 0; j < f->pcount[i]; j++) {
			n *= prime[i];
		}
	}
	return n;
}

int factor_count(factor *f) {
	int cnt = 1, i;
	for (i = 0; i < f->size; i++) {
		cnt *= f->pcount[i] + 1;
	}
	return cnt;
}

bool factor_greater(factor *f, factor *g) {
	// if needed, this function can be enhanced
	return factor_to_int(f) > factor_to_int(g);
}

bool factor_iter_next(factor *f, factor *start) {
	int i;
	if (is_factor_empty(f)) return false;

	for (i = 0; i < f->size; i++) {
		if (f->pcount[i] > 0) {
			f->pcount[i]--;
			break;
		}
		else {
			f->pcount[i] = start->pcount[i];
		}
	}
	return true;
}

void factor_print(factor *f) {
	int i;
	printf("f->size = %d\n", f->size);
	for (i = 0; i < f->size; i++) {
		printf("%4d", f->pcount[i]);
	}
	printf("\n");
}

void free_factor(factor *f) {
	free(f->pcount);
	free(f);
}


void main() {
	int i, j, tcount;
	int n = LAST - 1, x, y, t;
	int count = 0;
	int max = 0, fmax = 0;
	factor *fn, *ffn, *ff;

	init_primes();

	/*
	for (t = 1; t <= n; t++) {
		if (n*n % t == 0) {
			x = n + t;
			y = n + n * n / t;
			count++;
		}
	}
	printf("n = %d, count = %d\n", n, count);
	system("pause");
	*/

	while (true) {
		n++;
		count = 0;
		
		fn = factorize(n);
		ffn = factor_deep_copy(fn);
		factor_square(ffn);
		tcount = factor_count(ffn);
		
		if (fmax < tcount) {
			fmax = tcount;
			printf("n = %d, factor_count = %d\n", n, fmax);
		}

		if (tcount < ECOUNT) {
			free_factor(fn);
			free_factor(ffn);
			continue;
		}

		count = tcount - 1;

		ff = factor_deep_copy(ffn);
		while (factor_iter_next(ff, ffn)) {
			if (factor_greater(ff, fn)) {
				count--;
			}
		}

		free_factor(ffn);
		free_factor(fn);
		free_factor(ff);

		if (count > ECOUNT) {
			break;
		}
	}

	printf("n = %d, count = %d\n", n, count);
	system("pause");
}