나선모양 격자의 대각선상에 있는 소수의 비율 추적하기

[eng][kor]

구해야 할 것은 대각선 수에서 소수가 차지하는 비율인데, 나선을 둘러싸는 네모가 커질 때마다 꼭지점 네 개의 수만 이전의 대각선수 목록에 추가된다. 즉 기존 대각선수에 대한 소수 목록을 계속 갖고 있으면서 나선이 커질때마다 꼭지점 수를 추가해 나가면 된다. 꼭지점 네 개의 수는, 나선의 오른쪽 밑 꼭지점이 홀수 제곱이라는 문제의 힌트를 통해 쉽게 구할 수 있다.

실행시간 1.650 초.

/*
 	Problem 58 - Spiral primes
*/
	
#include <iostream>
#include <ctime>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

std::map<int,int> primes;
std::map<int,int> notprimes;
bool isprime( int n)
{
	if( n == 2) return true;
	std::map<int,int>::iterator it;
	it = notprimes.find(n); if( it != notprimes.end()) { return false; }
	it = primes.find(n); if( it != primes.end()) { return true; }

	int s = sqrt( n) + 1;
	for(int i=s; i>1; i--)
	{
		if (n%i ==0) { 
			notprimes.insert( std::map<int,int>::value_type( n, n));
			return false;
		}
	}

	primes.insert( std::map<int,int>::value_type( n, n));
	return true;
}

std::vector<int> getDiagonalNumbers( int size) 
{
	int bR = size * size; // bottomRight
	int bL = bR - size + 1; // bottomLeft
	int tL = bL - size + 1; // topLeft
	int tR = tL - size + 1; // topRight

	std::vector<int> dn;
	dn.push_back( bR);
	dn.push_back( bL);
	dn.push_back( tL);
	dn.push_back( tR);
	return dn;
}

int getnDiagonals( int size) { return ((size-1)/2)*4; }

int howmanyPrimes( std::vector<int> v)
{
	int n = 0;
	for(int i=0; i<v.size(); i++) {
		if( isprime( v[i])) { n++; }
	}
	return n;
}

double getDiagonalPrimeRatio( int size, double thisSizePrimes)
{
	return thisSizePrimes / getnDiagonals( size);
}

int main(int argc, char** argv)
{
	clock_t begin = clock();
	/* starting code */
	std::map<int, int> diagonalPrimes; // rectangleSize, nPrimes
	diagonalPrimes.insert( std::map<int,int>::value_type(1, 0));
	std::map<int, int>::iterator it;

	int size = 3;
	while(true)
	{
		std::vector<int> dn = getDiagonalNumbers( size);
		int p = howmanyPrimes( dn);
		
		it = diagonalPrimes.find( size-2);
		if (it != diagonalPrimes.end()) {
			diagonalPrimes.insert( std::map<int,int>::value_type(size, p + it->second)); 
		}
		double ratio = getDiagonalPrimeRatio( size, p+it->second); 
		if( ratio <= 0.1) break;
		size = size+2;
	}
	cout << "size=" << size << endl;

	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}