프로젝트 오일러 97

Large non-Mersenne prime

늘 쓰던 큰 수 클래스를 써서 푸니까 코드는 간단하지만 32초가 걸렸다. 10자리수까지만 계산범위를 제한했는데도..

/*
 	Problem 97 - Large non-Mersenne prime
*/
	
#include <iostream>
#include <ctime>
#include "BigInt.h"

using namespace std;

int MAX = 7830457;

int main(int argc, char** argv)
{
	clock_t begin = clock();

	BigInt n = BigInt(2);
	for(int i=1; i<MAX; i++)
	{
		BigInt mul = BigInt(2);
		n = n.multiply( mul, 10);
	}

	BigInt mul2 = BigInt(28433);
	BigInt one = BigInt(1);
	n = mul2 * n + one;

	string number = n.toString();
	cout << "number=" << number << endl;

	if (number.size() >= 10) cout << "solution=" << number.substr( number.size()-10, number.size()) << endl;

	clock_t end = clock();
	std::cout << "elapsed=" << double( end-begin) / CLOCKS_PER_SEC << endl;
}

괜찮다고는 생각했지만 인터넷을 찾아보니 bitshift 를 사용하는 훨씬 빠른 방법이 있었다. 실행시간 0.13초. 2제곱과 관련된 문제들을 풀 때 bitshift를 고려해야겠구나.

/*
 	Problem 97 - Large non-Mersenne prime
*/
	
#include <iostream>
#include <ctime>

using namespace std;

int MAX = 7830457;

int main(int argc, char** argv)
{
	clock_t begin = clock();

	unsigned long long n = 2;
	for(unsigned int i=1; i<=MAX; i++)
	{
		n = (n << 1) % 10000000000;
	}

	n *= 28433;
	n += 1;

	cout << "n=" << n << endl;

	clock_t end = clock();
	std::cout << "elapsed=" << double( end-begin) / CLOCKS_PER_SEC << endl;
}