TIL 6일차 - 소수판별알고리즘/반복문 복습

반복문

조건문/문자열은 이제 막힘없이 쭉쭉 풀 수 있는데 반복문이 문제다

그래도 어제보단 덜 헷갈리고 어떻게 푸는지 알게되었다.

예를들어

let output = characterAndNumber('hello');
console.log(output); // --> 'h0e1l2l3o4'

위와같이 나타내고싶으면

function characterAndNumber(str){
	let result = ''
    for(i=0;i<str.length;i++){    // index니까 0부터 i<str.length까지 원래수에서 1씩빼서 생각하면 편하다
      result = result + str[i] + i
    }
return result
}

시간이 좀 걸리지만 위와같이 구현해낼 수 있게 됐다.

소수판별알고리즘

소수란?
1과 자신 이외의 숫자로는 나누어지지 않는 자연수 (1은 소수가 아니고 2는 항상소수기 때문에 가능하면 1과 2는 미리 Boolean으로 정의해놓아야 편하다)

단순히 생각해보면
num까지 i++해서 하나하나 다 나눠보고 만약 나눠지는수가
if(num%i === 0 ) 이면 즉, 나눠떨어지는 수가 있다면 false 나눠지는 수가 없다면 true이다.

  • 1 이상의 자연수를 받아 소수인지의 여부를 판별하시오
function isPrime(num){
  if(num === 1){
    return false
  }
  if(num === 2){
    return true
  }
  for(i=2;i<num;i++){
    if(num%i === 0){
      return false
    }
  }
 return true
}

하지만 cs50에서 배운 시간복잡도를 생각해보면 위의 알고리즘은 효율적이지 않으므로 다른 알고리즘을 사용하는게 좋다.

소수검사할때 sqrt를 쓰면 좋은데, 어떤수의 약수는 무조건 대칭이되게 되어있다. 가령 36을 예로들면 1, 2, 3, 4, 6, 9, 12, 18, 36 처럼 (1,36),(2,18),(3,12),(4,9),(6,6)가 짝이 되므로 가운데를 기준으로 뒤에 큰 숫자들은 계산할 필요가 없는 것 이다.

그러므로 36에 sqrt을 씌워서 6을 기준으로 삼고 6의 약수중 나눠떨어지는 수가 1,6말고 없다면 이는 소수가 된다.그리고 소수는 무조건 홀수니까 2로 나누 떨어지지 않는다.

아래 예제를 통해 이해해보자.

  • 1 이상의 자연수를 받아 소수인지의 여부를 판별하시오
function isPrime(num){
  if(num === 1){
    return false
  }
  if(num === 2){
    return true
  }
  if(num%2 === 0){
    return false
  }
  for(i=3;i<=Math.floor(Math.sqrt(num));i=i+2){
   if(num%i === 0){
     return false
   }
  }
  return true
}

좋은 웹페이지 즐겨찾기