프로젝트 오일러 문제 풀이

gistfile1.js

// 2. 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

var first = 1;
var second = 2;
var total = 0;

while (second <= 4000000) {
    var third = first + second;
	
    if (second % 2 == 0) {
        total += second;
    }
	
    first = second;
    second = third;

}

console.log("total : " + total);

gistfile10.js

// 11. 20×20 격자에서 연속된 네 숫자의 곱 중 최대값

var map = [[08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08]
,[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00]
,[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65]
,[52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91]
,[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80]
,[24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50]
,[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70]
,[67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21]
,[24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72]
,[21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95]
,[78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92]
,[16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57]
,[86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58]
,[19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40]
,[04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66]
,[88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69]
,[04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36]
,[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16]
,[20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54]
,[01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]];



//격자 내 4개 수 곱의 최대값 (수평, 수직, 대각)
var max = 0;
var n = 20;
var val = [];

function solveMatrix() {
	
	// 가로 계산
	for (var inx = 0; inx < 20; inx++) {
		for (var jnx = 0; jnx < 17; jnx++) {
			
			var val1 = map[inx][jnx];
			var val2 =  map[inx][jnx + 1];
			var val3 = map[inx][jnx + 2];
			var val4 = map[inx][jnx + 3];
			var width =  val1 * val2 * val3 * val4;
			console.log(val1, val2, val3, val4);
			if (width > max) {
				max = width; 
				val = [val1, val2, val3, val4];
			}
		}	
	}
	
	// 세로계산
	for (var inx = 0; inx < 20; inx++) {
		for (var jnx = 0; jnx < 17; jnx++) {
			
			var val11 = map[jnx][inx];
			var val21 =  map[jnx + 1][inx];
			var val31 = map[jnx + 2][inx];
			var val41 = map[jnx + 3][inx];
			var height =  val11 * val21 * val31 * val41;
			console.log(val11, val21, val31, val41);
			if (height > max) {
				max = height; 
				val = [val11, val21, val31, val41];
			}
		}	
	}
		
	// 오른 대각 계산
	for (var inx = 0; inx < 17; inx++) {
		for (var jnx = 0; jnx < 17; jnx++ ) {
			
			var val1 = map[inx][jnx];
			var val2 = map[inx + 1][jnx + 1];
			var val3 = map[inx + 2][jnx + 2];
			var val4 = map[inx + 3][jnx + 3];
			var diagonal = val1 * val2 * val3 * val4;
			console.log(val1, val2, val3, val4);
			if (diagonal > max) {
				max = diagonal; 
				val = [val1, val2, val3, val4];
			}
		}
	}
	
	// 왼 대각 계산
	for (var inx = 3; inx < 20; inx++) {
		for (var jnx = 0; jnx < 17; jnx++ ) {
			
			var val1 = map[jnx][inx];
			var val2 = map[jnx + 1][inx - 1];
			var val3 = map[jnx + 2][inx - 2];
			var val4 = map[jnx + 3][inx - 3];
			var diagonal = val1 * val2 * val3 * val4;
			console.log(val1, val2, val3, val4);
			if (diagonal > max) {
				max = diagonal; 
				val = [val1, val2, val3, val4];
			}
		}
	}
	
	console.log(val);
	return max;
}

console.log("answer is " + solveMatrix());

gistfile2.js

// 3. 가장 큰 소인수 구하기

function findBiggestPrimeNumber(num) {
	
    var target = num;
    var biggestPrimeNumber = 1; 
	
    for (var inx = 2; inx <= target; inx++) {

        if (target % inx == 0) {
            
        	if (inx > biggestPrimeNumber) {
        		biggestPrimeNumber = inx;
        	}
        	
            target = target / inx;
            inx = 1;
        }
		
    }
	
    return biggestPrimeNumber;
	
}

gistfile3.js

// 4. 두개의 세자리 수 곱으로 만들 수 있는 가장 큰 대칭수 만들기

// 대칭수 검사
function isPalindrome (num) {
	
	var result;
	var temp = 0;
	
	for (var inx = num; inx > 0; inx = parseInt(inx/10)) {
		temp = (temp * 10) + (inx % 10);
	}
	
	if (num == temp) {
		result = true;
	} else {
		result = false;
	}
	
	return result;
}

// 두개의 세자리 수 곱으로 만들 수 있는 가장 큰 수 검색 
function solve () {
	
	console.log("solve start!!");
	
	var max = 0;
	
	for (var inx = 999; inx > 900; inx--) { // 다 돌릴 필요 없이 900대에서만 검사하면 될 듯
		
		for (var jnx = 999; jnx > 900; jnx--) {
			
			var target = inx * jnx;
			console.log("inx : " + inx + " jnx : " + jnx);
			
			if (isPalindrome(target)) {
				
				if (target > max){
					max = target;
					break;	
				}
			}	
		}
	}
	
	console.log("answer is " + max);
}

solve();

gistfile4.js

1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?// 5. 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

var solve = function () {
	
	var target = 1;
	
	while (1) {

		var flag = true;

		// 배수 검사
		for (var inx = 20; inx > 0; inx--) {
            if (target % inx !== 0) {
            	flag = false;
            	target++;
            	break;
            }  
		}
		
		if(flag) {
			return target;
		}
	}
	
};

console.log("answer is : " + solve());

gistfile5.js

// 6. 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?

var solve = function () {
	
	var sumOfSquared = 0;
	var sum = 0;
	
	for (var inx = 1; inx <= 100; inx++) {
	
		// 제곱의 합
		sumOfSquared += inx * inx; 
		
		// 합의 제곱
		sum += inx;
		
	}
	
	// 차이 계산
	return answer = (sum * sum) - sumOfSquared;
	
};

console.log("answer is : " + solve());

gistfile6.js

// 7. 10001번째의 소수

function solve() {
	
	var target = 2;
	var count = 0;
	
	while(1) {
		
		if (checkPrimeNumber(target)) {
			count++;
		}
		
		if (count == 10001) {
			break;
		}
		
		target++;
	}
	
	return target;
	
};

// 소수 체크
function checkPrimeNumber(num) {
	
	for (var inx = num - 1; inx > 1; inx--) {
		if (num % inx == 0) {
			return false;
		}
	}
	
	return true;
}

console.log("answer is : " + solve());

gistfile7.js

// 8. 1000자리 숫자 안에서 이어지는 5자리 숫자의 곱 중 최대값은?

function solve(numStr) {

	var arr = numStr.split("");
	var length = arr.length;
	var max = 0;

	for (var inx = 0; inx < length; inx++) {
		var target = Number(arr[inx]) * Number(arr[inx+1]) * Number(arr[inx+2]) * Number(arr[inx+3]) * Number(arr[inx+4]);
		
		if (target > max) {
			max = target;
		}
	}
	
	return max;
	
}


var numStr = "73167176531330624919225119674426574742355349194934"
	+"96983520312774506326239578318016984801869478851843"
	+"85861560789112949495459501737958331952853208805511"
	+"12540698747158523863050715693290963295227443043557"
	+"66896648950445244523161731856403098711121722383113"
	+"62229893423380308135336276614282806444486645238749"
	+"30358907296290491560440772390713810515859307960866"
	+"70172427121883998797908792274921901699720888093776"
	+"65727333001053367881220235421809751254540594752243"
	+"52584907711670556013604839586446706324415722155397"
	+"53697817977846174064955149290862569321978468622482"
	+"83972241375657056057490261407972968652414535100474"
	+"82166370484403199890008895243450658541227588666881"
	+"16427171479924442928230863465674813919123162824586"
	+"17866458359124566529476545682848912883142607690042"
	+"24219022671055626321111109370544217506941658960408"
	+"07198403850962455444362981230987879927244284909188"
	+"84580156166097919133875499200524063689912560717606"
	+"05886116467109405077541002256983155200055935729725"
	+"71636269561882670428252483600823257530420752963450";

console.log("answer is " + solve(numStr));

gistfile8.js

// 9. a + b + c = 1000 이 되는 피타고라스 수

function solve() {
	
	for (var a = 0; a < 500; a++) {
		
		for (var b = 0; b < 500; b++) {
			
			for (var c = 0; c < 500; c++) {
			
				if (a * a + b * b == c * c) {
					
					if (a + b + c == 1000) {
						return a * b * c;
					}
					
				}
				
			}
			
		}
		
	}
}

console.log(solve());

gistfile9.js

// 10. 이백만 이하 소수의 합

/* Sieve of Eratosthenes (에라토스테네의 체)
* 2를 제외한 모든 소수는 홀수이므로, 어떤 수 n이 짝수이면 소수가 아님
* N이 합성수라면 N = a * b 형태가 되므로 (a>1 && b>1) a와 b 둘 중 하나는 
* sqrt(N) 보다 작거나 같다.
* 그러므로 N을 2부터 sqrt(N)까지 나눠보아 나누어지지 않으면 N은 소수가 됨
* 어떤 수 P가 소수이면 P로 나눌 수 있는 P의 배수들은 소수가 아님
*/

var eratosthenes = function(n) {
	
	console.log("start!!");
	
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // All array[i] set to true are primes
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    var length = output.length;
    var sum = 0;
    for (var inx = 0; inx < length; inx++) {
    	sum += output[inx];
    }
    
    return sum;
};

console.log(eratosthenes(2000000));