자바스크립트 숫자 #3

자바스크립트 숫자 객체

정수 반올림

자바스크립트가 모든 숫자를 나타낼 땐 부동소수점을 사용함
그렇기 때문에 정수 나눗셈은 소용이 없음
예를 들어 다른 모든 프로그램언어에서는 5/4 같은 경우 몫인 1로 값을 갖지만

자바스크립트에서는 5/4의 결과는 부동소수점임

5/4; // 1.25

자바스크립트에서 정수나눗셈을 원한다면 ceil이나 round, floor를 사용하면 됨

Number.EPSILON

두 개의 표현 가능한 숫자 사이의 가장 작은 간격을 반환

최대치와 최소치

Number.MAX_SAFE_INTEGER는 가장 큰 정수를 반환 (1.7976931348623157e+308)
Number.MIN_SAFE_INTEGER는 가장 작은 정수를 반환 (-9007199254740991)

무한

Number.MAX_SAFE_INTEGER보다 큰 유일한 것은 Infinity임

---

숫자 알고리즘

소수 검증

숫자가 소수인지 알아보려면 숫자 n을 n부터 n-1까지의 수로 나눠 나머지가 0인지를 확인하면 됨

function isPrime(n) {
	if ( n <= 1) {
    	return false;
	}
    
    // 2부터 n-1까지의 수로 나눔
    // 2부터 자기자신 전까지 다 넣어본 후 if문에 걸리지 않는다면 true를 리턴
    for (var i=2; i<n; i++) {
    	if (n%i == 0) {
        	return false;
		}
	}
    
    return true;
}    

시간 복잡도 O(n) (빅 오 오브 n)
위 알고리즘은 0부터 n까지의 모든 수를 확인 하기 때문에 O(n)이다

다음 방식에서 패턴을 찾아 알고리즘을 더 빠르게 만들 수 있는 방법
1. 2의 배수는 무시함
2. 2와 3을 제외하고는 모든 소수는 6k +- 1의 형태를 지님

또한, n이 소수인지 알아보기 위해선 반복문을 n의 제곱근까지만 확인해보면 됨
n의 제곱근이 소수가 아니면 n은 수학 정의에 의해 소수가 아니기 때문
(제곱근은 제곱의 반대개념)

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  // 입력한 숫자가 2또는 3일 경우는 바로 true 반환

  // 6의 배수인지 검사
  if ( n % 2 == 0 || n % 3 == 0) return false;

  for (var i=5; i*i<n; i=i+6) {
    // 5나 7로 (6의 배수의 +-1 인지 검사)
      if ( n % i == 0 || n % ( i + 2 ) == 0)
        return false;
  }

  return true;
}

시간 복잡도 O(sqrt(n))
이렇게 개선한 알고리즘은 시간 복잡도를 훨씬 줄일 수 있음

소인수 분해

소수는 암호화와 해싱의 기반이 되고 소인수분해는 주어진 숫자를 만들기 위해 어떤 소수들이 곱해져야 하는지 구하는 과정

function primeFactors(n) {
    // n이 2로 나누어진다면 2로 나누어 질 때까지 계속 n을 나눔 (짝수만 가능, 홀수는 나머지 존재함)
    while (n%2 == 0) {
      console.log(2)
      n = n/2;
    }

    // 여기선 홀수를 다루니까 수를 3부터 2씩 증가시켜서 나눠봄
    for (var i = 3; i*i <= n; i = i+2) {
      // i가 n을 나눌 수 있는 한 계속해서 i가 출력되고 n을 i로 나눔
      while (n%i == 0) {
        console.log(i);
        n = n/i;
      }
    }

    // 다음 조건문은 n이 2보다 큰 소수인 경우를 처리하기 위한 것 
    if (n > 2) {
      console.log(n)
    }
}

primeFactors(10) // 5와 2가 출력

시간복잡도 O(sqrt(n))

위의 알고리즘은 i로 나머지가 없이 나눌 수 있는 모든 수를 출력
소수가 함수의 입력값으로 전달된 경우 아무런 수도 출력이 되지 않다가 마지막 조건문에서
출력이 되지 않는 이유는 당연하게도 짝수, 홀수에 나누어 진다는 것은 소수가 아니란 소리기 때문
들어온 n이 2보다 큰지 확인한 경우 n이 출력

---

연습문제 1

n보다 작은 소수 출력하기

function isPrime(n) {
	if ( n <= 1) {
    	return false;
	}
    
    // 2부터 n-1까지의 수로 나눔
    // 2부터 자기자신 전까지 다 넣어본 후 if문에 걸리지 않는다면 true를 리턴
    for (var i=2; i<n; i++) {
    	if (n%i == 0) {
        	return false;
		}
	}
    
    return true;
}

function AllisPrime(n) {
  for (var i=0; i<n; i++)
  {
    if (isPrime(i)) {
      console.log(i)
    }
  }
}

AllisPrime(15) // 2, 3, 5, 7, 11, 13 출력 

시간 복잡도 O(sqrt(n))