Project Euler #58 (Spiral primes)

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

Spiral prime을 계산하여 10% 이하가 될 때를 구한다.

간단한 문제이므로 코드에 대한 설명은 생략한다.

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

#define RATIO 10

bool is_prime(int p) {
	int i;
	for (i = 2; i <= (int)sqrt(p); i++) {
		if (p%i == 0) return false;
	}
	return true;
}

void main() {
	int length, half = 3;
	int count = 8, tot = 13;
	int n = 49;
	int i;
	while (true) {
		half++;
		length = half * 2 + 1;
		for (i = 0; i < 4; i++) {
			tot++;
			n += (length - 1);
			if (is_prime(n)) count++;
		}
		if (count*RATIO < tot) break;
	}

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