소수(prime number)여부 판별하기

Q. 1 이상의 자연수를 입력 받아서 소수(prime number)인지 여부를 리턴하세요.

---

 

입력 : int type 의 수

출력 : boolean type 을 리턴

 

---

내가 처음 작성한 코드

public class Solution { 
    public boolean isPrime(int num) {
    if(num == 1) return false;
    if(num == 2) return true;
 
    for(int i = 2; i < num; i++) {
      if(num%i == 0) return false;
    }
    return true;
    } 
}

---

나의 로직 및 생각

• 숫자 1은 소수가 아니므로, 조건문을 사용하여 우선적으로 제거.
• 숫자 2를 조건문을 사용하여 우선적으로 제거하지 않으면, 아래 기입한 반복문 code 에서 숫자 2를 소수가 아닌 값(false) 로 리턴하기 때문에, 숫자 2를 조건문을 사용하여 우선적으로 제거함.
• 숫자 1 과 2 는 앞선 조건문을 통해서 우선적으로 처리가 됨으로, 반복문의 num 변수에 들어가는 값은 최소 3 부터 이다.
• 숫자 2 부터 ~ 입력된 값num  까지 모든 숫자를 num 에 나눠 보면서, 그 나머지를 확인한다.
   만약 나머지가 0 이라면 그 때의 num 은 소수(prime number)가 아닐 것이다.
• 이때 입력된 값 num 은 제외하기 위해서 부등호에 등호를 넣지 않는다.
   등호를 넣게 되면 자기 자신을 나누게 되고, 이럴 경우 반드시 나머지가 0이 된다.
   그러면 그 때의 num이 prime number 일지라도 prime number 가 아니라는 값(false)를 리턴하게 된다.
   즉, 의도치 않은 결과값을 리턴 받게됨으로, 자기 자신은 나누지 않는다.

---

나의 코드의 문제점 및 보완점

• 입력받는 값num이 매우 큰 수 일 경우, 처리해야하는 계산 횟수가 매우 크게 증가한다.
  입력 값이 242425235 라는 값이라면, 2 부터 242425234 까지, 즉 총 242425233 회를 나머지를 구하는 연산을 해야한다.
  
• 코드를 개선하여 원치 않는 경우의 수는 제거하여 보다 효율적으로(적은 연산 횟수) 작동하게끔 해보자.
• 소수(prime number)의 수학적 특징을 고려하여 이를 코드에 반영하면 연산 횟수가 보다 줄어든다.

---

개선한 코드

public boolean isPrime(int num) {
        if(num == 1 || num%2 == 0) return false;
        if(num == 2) return true;
 
        int sqrt = (int) Math.sqrt(num);
        for(int i= 3; i <= sqrt; i += 2) {
            if(num%i == 0) return false;
        }
        return true;
    }

---

고려한 점 및 개선한 점

• 숫자 2를 제외하고는, 짝수 중에는 prime number 가 없다.
  - 숫자 2는 조건문으로 우선적으로 제거한다.
  - 짝수도 조건문을 사용하여 경우의 수를 제거한다.
  - 이때 짝수를 제외시키는 코드를 먼저 작성하게 되면 숫자 2를 소수가 아닌 수로 인식한다!!
• 숫자 2 와 짝수는 앞선 조건문을 통해 경우의 수를 제거 했기 때문에, 반복문을 통해서 확인하는 값은 숫자 3부터 시작하여 홀수만 검사하게 될 것이다.
• 홀수 / 짝수 는 절대 나누어 떨어지지 않는다.
  - 나누어 떨어지지 않는다는 뜻은 num%i == 0 의 결과값이 항상 false 가 나온다는 것이고, 이렇게 항상 확실한 결과값이 나오는 경우의 수는 반복문을 통해 확인할 필요가 없다.
  - 예를 들어 15 가 소수인지 검사하기 위해 3 부터 14까지의 숫자를 나눠본다면, 15/4, 15/6, 15/8, 15/10. 15/12, 15/14 는 항상 무조건 나누어 떨어지지 않는다. 짝수로 나누어보는 경우의수는 확인할 필요가 없다.
• 항상 홀수로 나누어 보도록 하기 위해서 i + = 2 코드를 반복문 증감식에 넣는다.
  - 이러면 3, 5, 7, 9 ... 라는 홀수만 나누어 보게 될 것이다.
• 입력된 값num의 약수들을 오름차순으로 정렬해보면, num의 제곱근 값을 기준으로 데칼코마니 형태이다
  - 즉, "입력된 값num 의 제곱근 보다 크고 num 보다 작은 값" 들은 num에 나눠서 검사해 볼 필요가 없다.
  - 왜냐하면, "숫자 3부터 num의 제곱근 보다 작은 자연수" 들을 num 에 나누어 볼 때, 이미 검사한 항목들이기 때문이다.
• Math.sqrt(num) 는 미리 계산해 두고 변수에 그 값을 저장해 둔다.
  - 그렇지 않으면 반복문에서 값을 검사할 때마다  매번 Math.sqrt(num) 함수를 계산하게 된다.
  - Math.sqrt(num) 를 단 한번 계산해두고 그 값을 변수에 저장해 둔다면, 함수가 반복적으로 계산될 필요가 없어진다.

 

 

22년 12월 23일 학습