/*
    1から始めて, 以下のように反時計回りに数字を並べていくと, 
    辺の長さが7の渦巻きが形成される.
    面白いことに, 奇平方数が右下の対角線上に出現する. 
    もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. 
    ここで割合は8/13 = 62%である.

    渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 
    以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.
*/

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

bool isPrime(int num) {
    int i;

    if( num < 2 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for( i = 3; i * i <= num; i += 2 ) {
        if( num % i == 0 ) return false;
    }

    return true;
}

int main(void) {
    int num = 1;
    int primeCnt = 0, sideLen = 1;
    int add = 2;
    int i;

    while( true ) {
        sideLen += 2;
        for( i = 0; i < 4; i++ ) {
            num += add;
            if( isPrime(num) ) {
                primeCnt++;
            }
        }

        if( (double)primeCnt / (2 * sideLen - 1) < 0.1 ) {
            printf("%lld\n", sideLen);
            break;
        }
        add += 2;
    }

    return 0;
}