Problem 10

이백만 이하 소수의 합

문제

10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.
이백만(2,000,000) 이하 소수의 합은 얼마입니까?

풀이 (본인)

var num = 2;
var result = 0;
while(num<2000000){
  var priNum = true;
  for(var divNum = 2; divNum < num; divNum++){
    if(num%divNum === 0){
      priNum = false;
      break;
    }
  }
  if(priNum){
    result += num;
  }
  num++
}
console.log(result)

풀이 (다른 사람)

var num = 2;
var arr = [2];
var sum = 2;
while(num < 2000000){
    num++;
    for(var i=0;i<arr.length;i++){
        if(num%arr[i] == 0)
            break;
        if(i == arr.length-1){            
            arr.push(num);
            sum += num;
        }
    }  
};
console.log(sum)

npm middleware 사용하여 소수의 합 구하기

sieve-of-eratosthenes는 에라스토테네스의 체를 이용한 알고리즘입니다.

npm install sieve-of-eratosthenes

위 코드를 실행하여 sieve-of-eratosthenes를 설치합니다.

node REPL을 통해서 위 사진과 같이 계산이 가능하다.

배운점

• 배열을 이용해서 소수들로 나눠보고 나누어지지 않는다면 소수를 추가하는 코드를 작성하니 속도가 10배정도 차이났다.
• 에라토스테네스 체를 이용하여 소수의 계산을 획기적으로 계산 할 수 있다.(1초 안에 연산가능)

느낀점

• 에라토스테네스 체를 알았지만 실제로 구현하기는 어렵다.(지금 상태에서….)