소수점판별

수민·2023년 1월 19일

알고리즘

목록 보기

16/22



function isPrime(num) {
  
  if(num === 2) {
    return true;
  }
  
  for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
    if(num % i === 0){
      // 한 번이라도 나누어 졌으니 소수가 아니므로 return false
      return false; 
    }
  }
  // 나눠진 수가 없다면 해당 수는 소수이므로 return true
  return true; 
}



function isPrime(num) {
  if(num === 2)
  return true;

  for(let i = 2; i<num; i++){
    if(num % i === 0){
      return false;
    }
  }
  return true;
}




 

2부터 소수를 판별할 수 있으니 2를 먼저 return 해주고
나머지는 반복문을 이용해 나눠지는 수가 있는지 계산해보고 
나눠지만 false를 return 해주고 for문을 빠져나올때까지 
나눠지는 수가 없다면 true를 리턴해준다. (이때의 시간복잡도는 O(N) 이다.)



function isPrime(num) {
  if(num === 2)
  return true;

  for(let i = 2; i<=num/2; i++){
    if(num % i === 0){
      return false;
    }
  }
  return true;
}



 

다음은 두번째 방법이다. 이것도 첫번째 방법과 같지만 for문을 좀 더 적게 돌릴 수 있다. 

num의 약수는 num의 절반을 넘을 수 없기 때문이다. (시간복잡도는 O(N) 이다.)

소수란?

소수란 1과 자신만으로 나누어 떨어지는 1보다 큰 양의 정수를 뜻합니다.

2, 3, 5, 7, 11, 13... 와 같은 수는 소수가 됩니다.

소수를 구하는 3가지의 방법을 알아보겠습니다.

n까지 판별하기

1이 아닌 2부터 n사이의 모든 정수를 다 나누어 떨어지는 수가 있는지 확인하는 방법입니다.


const isPrime=(n)=>{
  
  for(let i=2; i<n; i++){
    if(n%i===0){
      return false;
    }
  }
  return true;

n의 제곱근 판별하기

n의 제곱근 (√n) 값으로 나누어 떨어지면 √n의 배수라는 뜻이므로 소수가 아니게 됩니다.

예를 들어보자면 25의 제곱근은 √25(5) 입니다.

이때 5까지만 반복문이 돌아가더라도 25는 5의 배수이므로 i가 5일 때 나누어 떨어지게 되고 소수가 아님을 판별할 수 있게 됩니다.

다른 예시로 49의 제곱근은 √49(7)입니다. 49도 7의 배수이므로 i가 7일 때 나누어 떨어지므로 소수가 아님을 알 수 있습니다.

즉 처음에 소개한 2, 3, 5, 7, 11, 13... 의 배수까지는 비교할 필요가 없습니다.

하지만 1은 소수가 아니기에 따로 구분을 해줘야합니다


const isPrime=(n)=>{
	if(n<2) return false;
  for(let i=2; i<Math.ceil(Math.sqrt(n)); i++){
   	if(n%i===0){
     return false; 
    }
  }
  return true;
}