숫자 2 부터 특정 자연수 까지의 모든 소수(prime number)들을 모으기

Q. 2 이상의 자연수를 입력 받아서, 2 부터 해당 수 까지의 모든 소수(prime number)를 모아서 리턴하세요.

---

입력 : int type 의 수 (단, 2 이상의 수)

출력 : String type 을 리턴 ,  2-3-5-7 의 형태로 리턴

---

내가 처음 작성한 코드

public String listPrimes(int num) {
      String answer = "2";
      if(num==2) return "2";
 
        for(int i = 3; i <= num; i++) {
            boolean prime = true;
            
            for(int k = 2; k < i; k++) {
                if(i % k == 0) {
                    prime = false;
                    break;
                }
            }
            if(prime) {
                answer+= "-" + i;
            }
        }
        return answer;
    }

---

나의 로직 및 생각

• 숫자 2 부터 특정 숫자 까지의 그 사이에 있는 모든 숫자 들을 나열하고(반복문), 그 모든 숫자들을 전부 각각 소수인지 판별(반복문) 해야 하기 때문에 중첩 for 문을 사용하기로 했다.
• inner 반복문에서 소수 임을 판별하는 로직은 이전에 작성한 포스트(소수(prime number)여부 판별하기)와 같은 로직으로 작성했다.
• boolean type 변수를 선언해 두고, 해당 변수가 true 일 때만 answer 변수에 숫자를 넣도록 조건문을 작성하였다.
  - inner 반복문에서 i % k == 0 인 경우, 해당 i 값은 소수가 아니기 때문에 선언해 둔 boolean type 변수에 false 를 대입 하도록 하였다.
• inner 반복문에서 숫자 k 부터 숫자 i 까지 꼭 반드시 모든 숫자를 검사해 볼 필요 없었다.
   - 따라서, 순차적으로 숫자 k 부터 i 까지 숫자 하나씩 검사하다가 i % k == 0 가 true 임을 발견하는 즉시 바로 inner 반복문을 벗어나고 다음 숫자인 i+1 을 검사해도 되기 때문에 break 를 작성하였다.

---

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

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

---

개선한 코드

public String listPrimes(int num) {
        String answer = "2";
 
        if(num == 2) return "2";
 
        for(int test = 3; test <= num; test += 2) {
            boolean prime = true;
            int sqrt = (int) Math.sqrt(test);
            for(int div = 3; div <= sqrt; div += 2) {
                if(test % div == 0) {
                    prime = false;
                    break;
                }
            }
            if(prime) answer += "-" + test;
        }
        return answer;
    }

---

고려한 점 및 개선한 점

• 숫자 2를 제외하고는, 짝수 중에는 prime number 가 없다.
• 따라서 반복문을 통해서 확인하는 값은 숫자 3부터 시작하여 홀수만 검사하는 것이 효율적이다.
     for(int test = 3; test <= num; test += 2) {  // outer 반복문의 증감식
  
  
• 홀수 / 짝수 는 절대 나누어 떨어지지 않는다.
  - 홀수 / 짝수가 절대 나누어 떨어지지 않는다는 뜻은 홀수인 test를 짝수인 div로 나누어서 test가 소수인지 확인해볼 필요가 없다는 뜻이다. 왜냐하면 test % div == 0 는 항상 무조건 false가 나올 것이기 때문에.
  - 예를 들어 15 가 소수인지 검사하기 위해 3 부터 14까지의 숫자를 나눠본다면, 15/4, 15/6, 15/8, 15/10. 15/12, 15/14 는 항상 무조건 나누어 떨어지지 않는다. 따라서 홀수를 짝수로 나누어보는 경우의수는 확인할 필요가 없다.
• 항상 홀수로 나누어 보도록 하기 위해서 i + = 2 코드를 반복문 증감식에 넣는다.
    for(int div = 3; div <= sqrt; div += 2) {  // inner 반복문의 증감식
• test 의 약수들을 오름차순으로 정렬해보면, test 의 제곱근 값을 기준으로 데칼코마니 형태이다
  - 즉, "test 의 제곱근 보다 크고 test 보다 작은 값" 들은 div 로 나눠서 검사해 볼 필요가 없다.
  - 왜냐하면, 위의 경우는 "숫자 3부터 test 의 제곱근 보다 작은 자연수" 들을 div 로 나누어 볼 때, 이미 검사한 항목들이기 때문이다.
• Math.sqrt(test) 는 미리 계산해 두고 변수에 그 값을 저장해 둔다.
  - 그렇지 않으면 반복문에서 값을 검사할 때마다  매번 Math.sqrt(test) 함수를 계산하게 된다.
  - Math.sqrt(test) 를 계산해두고 그 값을 변수에 저장해 둔다면, 함수가 반복적으로 계산되어질 필요가 없어진다.

 

 

22년 12월 23일 금요일 학습