Project Euler 58

C/C++ Project Euler

1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≈ 62%である.

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

#include <iostream>
using namespace std;

bool isPrime(long long num){
	for(long long i=3 ; i<num/2 ; i++){
		if(num%i==0) return false;
	}
	return true;
}

int main(){
	long long allnum=1, primenum=0;

	long long i,k;
	for(i=2 ; ; i++){
		for(int j=1 ; j<4 ; j++){
			k = 4*i*i - (4+2*j)*i+(1+2*j);
			if(isPrime(k)){
				primenum++;
			}
		}

		allnum+=4;

		cout << i << " " << (double)primenum/(double)allnum << endl;
		if((double)primenum/(double)allnum < 0.1) break;
	}
	cout << 2*i-1 << endl;

	int end;
	cin >> end;
}

プログラム動かして寝て、朝起きたらできてたというレベルなので計算時間的にはダメ。書き直したいが今はいい方法が思いつかない。