소수

: 1과 자기 자신만을 약수로 가지는 수
2, 3, 5, 7, 11, 13, 17, 19 ...

---

기본적인 풀이

1. 자기 자신보다 작은 숫자(i)로 모두 나누어 봤을 때,

• 나누어 떨어지는 수가 있다면, 소수가 아니다.
• 나누어 떨어지는 숫자가 없다면, 소수이다.

2. 모든 숫자는 1로 나누어 떨어지기 때문에, i에서 1은 제외하고 i는 2부터 시작해야 한다.

function isPrimeNumber(num) {
    if(num === 1) return false; // 1은 소수가 아니므로 false를 반환한다.
  
	for(let i = 2; i < num; i++) { // 자기 자신보다 작은 숫자로 모두 나누어봤을 때
    	if(num % i === 0) return false; // 약수가 하나라도 있으면 소수가 아니다.
    }
  return true; // 약수가 하나도 발견되지 않으면 소수이다.
}

➡️ 하지만 위의 알고리즘의 시간 복잡도는 O(N)이며 매우 비효율적이다.
(i가 2부터 num까지) 모든 경우의 수를 다 돌며 약수인지 여부를 확인해야 하기 때문이다.

시간 복잡도(Time Complexity)

: 알고리즘을 실행하는 데 걸리는 시간의 양
시간 복잡도가 높을수록 비효율적인 알고리즘, 낮을수록 효율적인 알고리즘이다.

---

제곱근을 이용한 풀이

이 시간복잡도를 O(N½)으로 계산할 수 있는데, 바로 제곱근을 이용하는 것이다.

1. 모든 약수들은 대칭을 이룬다.

• 36의 약수

1	2	3	4	6	6	4	3	2	1
36	18	12	9	6	6	9	12	18	36

---

2. 따라서 그 숫자의 제곱근까지만 약수인지 여부를 확인하면 된다.

• 36이 약수인지 확인하기 위해 i = 2, 3, 4, 5, 6으로만 나누어보면 된다.

function isPrimeNumber(num) {
  let squareRoot = Math.sqrt(num); // squareRoot라는 변수를 만들어 num의 제곱근을 할당한다.
  
  if(num === 1) return false; // 1은 소수가 아니므로 false를 반환한다.
  
  for(let i = 2; i <= squareRoot; i++) { // num의 제곱근 이하의 모든 숫자로 나누어봤을 때
    if(num % i === 0) return false; // 약수가 하나라도 있으면 소수가 아니다.
  }
  
  return true; // 약수가 하나도 발견되지 않으면 소수이다.
}

---

3. 이때, i가 홀수인 수만 돌며 약수의 여부를 확인하도록 하면 시간 복잡도를 조금 더 개선할 수 있다.

• 36이 약수인지 확인하기 위해 i = 3, 5로만 나누어보면 된다.

function isPrimeNumber(num) {
  let squareRoot = Math.sqrt(num); // squareRoot라는 변수를 만들어 num의 제곱근을 할당한다.
  
  if(num === 1) return false; // 1은 소수가 아니므로 false를 반환한다.
  
  if(num === 2) return true; // 2는 소수이므로 true를 반환한다.
  
  if(num % 2 === 0) return false; // 짝수는 false를 반환한다.
  
  for(let i = 3; i <= squareRoot; i += 2) { // num의 제곱근 이하의 3부터 모든 홀수로 나누어봤을 때
    if(num % i === 0) return false; // 약수가 하나라도 있으면 소수가 아니다.
  }
  
  return true; // 약수가 하나도 발견되지 않으면 소수이다.
}

❔ 학습 후 궁금한 점

• 시간 복잡도는 무엇인지?
• 에라토스테네스의 체는 무엇인지?