소수 찾기

1차시도.

왜 안되나 했더니.. numbers는 배열이 아닌데 push를 하고 있었다.

function solution(n) {
  let numbers = 0
  let countofnotsosu = 0
  for (let i=1; i<n+1; i++){
    numbers.push(i)
    for (let h=2; h<numbers; h++){
      if(numbers%h === 0){
        countofnotsosu ++
        numbers = 0
      }
    }
  }
  return countofnotsosu
}

수정해서 다시 해보면 소수가 아닌 숫자의 갯수가 6이 아닌 5가 출력.
for (let h=2; h<numbers; h++) 여기에서 numbers에 2가 들어갈 때 범위가 제대로 잡히지 않아서 값이 출력되지 않는다.
강제로 숫자를 +1 해줘서 갯수를 맞춰야할까..?

function solution(n) {
  let numbers = 0
  let countofnotsosu = 0
  for (let i=1; i<n+1; i++){
    numbers = i
    for (let h=2; h<numbers; h++){
      if(numbers%h === 0){
        countofnotsosu ++
        numbers = 0
      }
    }
  }
  return countofnotsosu
}
//solution(10)
//5

미완성 1.

값은 나오지만 시간 초과라서 테스트 케이스 마지막 3개와 효율성은 실패가 나온다.

function solution(n) {
  let numbers = 0
  let countofnotsosu = 0
  for (let i=1; i<n+1; i++){
    numbers = i
    
    for (let h=2; h<numbers; h++){
      if(numbers%h === 0){
        countofnotsosu ++
        numbers = 0
        break
      }
    }
  }
  return n - countofnotsosu -1
}

미완성2.

루트를 사용해서 for문이 도는 시간을 단축.
했지만 효율성에서 시간초과로 실패..

function solution(n) {
  let numbers = 0
  let countofnotsosu = 0
  for (let i=1; i<n+1; i++){
    numbers = i
    
    for (let h=2; h <= Math.sqrt(numbers); h++){
      if(numbers%h === 0){
        countofnotsosu ++
        numbers = 0
        
      }
    }
  }
  return n - countofnotsosu -1
}

미완성4.

하나라도 줄여보겠다고 i=1에서 i=2로 바꿨다. 진짜 쪼끔 줄어들었다.

function solution(n) {
  let numbers = 0
  let countofnotsosu = 0
  for (let i=2; i<n+1; i++){
    numbers = i
    
    for (let h=2; h <= Math.sqrt(numbers); h++){
      if(numbers%h === 0){
        countofnotsosu ++
        numbers = 0
        break
      }
    }
  }
  return n - countofnotsosu -1
}

완성본.

결국 다른 분들이 푼 걸 참고..
사실 아직도 와.. 이걸 사람의 머리로 짰다고? 하는 중
에라토스테네스의 체..

function solution(n) {
  let arr = Array(n+1).fill(true).fill(false, 0, 2)
  for (let i = 2; i*i <= n; i++){
    if(arr[i]){
      for(let j = i*i; j <= n; j += i){
        arr[j] = false
      }
    }
  }
  return arr.filter(e => e).length
}

어떤 형식으로 코드가 나오는지 보고자 코드를 덜어내보았음.

for (let i = 2; i*i <= 50; i++){
    
      for(let j = i*i; j <= 50; j += i){
        console.log(j)
      }
    
  }