[Java][프로그래머스][Level 1] 소수 찾기 - 3가지 방법 이용

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

생각

소수를 찾는 문제는 프로그래밍을 공부하다보면 대부분의 사람들이 보게 되는 문제이다. 

가장 쉬운 첫 번째 방법은, 2부터 n까지의 숫자 배열을 만들고 다시 2부터 나눠서 만약 자기 자신으로만 나누어 떨어진다면 소수로 입력하는 것이다. (1은 소수가 아니기에 처음부터 배제한다.) 제한 조건에 n은 1,000,000(백만)이므로 위 방법을 사용하면 시간이 오래 걸릴 것이다. (후에 3가지 방법 모두 실행 속도를 비교할 것이다.) 이 방법도 n까지 모두 나누어 보면서 비교해보는 방법이 아닌 2~n-1까지 나누어지면 바로 break하는 방법을 사용해서 최대한 실행 수를 줄인다.

 

두번 째 방법은, 조금은 수학적인 접근을 하는 것이다. 자연수 n이 소수이기 위한 필요 충분 조건은 n이 n의 제곱근보다 작은 어떤 소수로도 나눠지지 않는다. 수를 수로 나누어 떨어진다면 그떄의 몫은 반드시 그 수의 제곱근보다 작기 때문이다. 첫 번째 방법에서 범위를 n이 아닌 sqrt(n)으로 설정하면 된다.

마지막 방법은 에라토스테네스의 체를 이용한 방법이다. 이 방법은 중1 수학 교과서에서도 나오는 내용이니 크게 어렵지 않을 것이다. 방법은 아래와 같다.

1. 2부터 n까지의 모든 수를 나열한다.

2. 2는 소수이므로 소수로 입력한다. 후에 2의 배수들은 소수가 아니게 되므로 n까지의 자기 자신을 제외한 2의 배수를     모두 지운다.

3. 3은 소수이고 2의 배수가 아니므로 지워지지 않았다. 똑같이 n까지의 3의 배수를 모두 지워준다.

4. 5도 소수이고 지워지지 않았다. n까지의 5의 배수를 모두 지워준다.

5. n의 제곱근전의 최대 소수까지 반복해준다.

[ 120까지의 소수를 구하는 방법 출처: 위키피디아 ]

코드

첫 번째 방법 (1~n까지 n이하의 모든 수로 각각 나누어 본다.) + 두번 째 방법 / 속도 비교

 

class Solution {
      public int solution(int n) {
          int answer = 0;
                    
          for(int i=2; i<=n; i++) {
              boolean flag = true;
              for(int j=2; j<i; j++) { //두 번째 방법에서는 j<i 부분을 j<Math.sqrt(i) 로 바꾼다.
                  if(i%j==0) {
                      flag = false;
                      break;
                  }
              }
              
              if(flag==true) answer++;
          }
          
          return answer;
      }
    }

[ 첫 번째 방법 실행 결과 ]

[ 두 번째 방법 실행 결과 ]

 

 

 

 

 

 

세번째 방법 (에라토스테네스의 체 이용)

 

class Solution {
      public int solution(int n) {
          int answer = 0;
          
          int[] number = new int[n+1];
          
          //2부터 n까지의 수를 배열에 넣는다.
          for(int i=2; i<=n; i++) {
              number[i] = i;
          }
          
          //2부터 시작해서 그의 배수들을 0으로 만든다.
          //후에 0이면 넘어가고 아니면 그의 배수들을 다시 0으로 만든다.
          for(int i=2; i<=n; i++) {
              if(number[i]==0) continue;
              
              for(int j= 2*i; j<=n; j += i) {
                  number[j] = 0;
              }
          }
          
          //배열에서 0이 아닌 것들의 개수를 세준다.
          for(int i=0; i<number.length; i++) {
              if(number[i]!=0) {
                  answer++;
              }
          }
          
          return answer;
      }
    }

속도가 엄청난 차이를 보인다. 첫 번째 방법에서는 아예 시간 초과가 떴고, 두번째와 세번쨰를 비교해보면 약 10배 정도의 속도 차이를 보여준다. 이래서 코딩을 하는데도 수학 지식이 필요한 것 같다.