자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 소수 (에라토스테네스 체)

https://hyejin.tistory.com/1212

자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 피보나치 수열

-> 이전 문제 풀이 

 

 

 

5. 소수 (에라토스테네스 체) 

 

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력

첫 줄에 소수의 개수를 출력합니다.

 

예시 입력 1 

20

 

예시 출력 1

8

 

 

문제 풀이 1

public int solution(int num)
{
   int answer = 0;
   
   for (int i = 2; i <= num; i++)
   {
      int cnt = 0;
      for (int j = 1; j <= i; j++)
      {
         if (i % j == 0)
         {
            cnt++;
         }
      }
      if (cnt <= 2)
      {
         answer ++;
      }
   }
   
   return answer;
}

👩‍💻 : 우선 이건 내가 푼 방식인데 이렇게 하면 타임 아웃이 난다. 채점 사이트 시간 제한이 1초여서 num의 값으로 20만 을 주면 시간 제한에서 걸린다.. 소수 구하는 방법으로 에라토스테네스 체를 사용하라는 것 같은데 그 방식은 모르고... 다른 방법으로 구하자니 머리가 안돌아가서... 처음으로 문제 정답 처리 전에.. 강의를 봤다... 

 

암튼 내가 푼 방식은 이중 for문을 돌면서 i % j == 0이면 cnt 의 값을 증가해주고, 두번째 for문을 나와서 cnt가 2보다 크면 소수가 아니라는 말이기 때문에 answer에 1 더하지 않고, 2보다 이하일 경우에만 1 더하도록 해서 리턴했다. 

 

 

 

문제 풀이 2

public int solution2(int n)
{
   int answer = 0;
   int[] ch = new int[n + 1];
   
   for (int i = 2; i<= n; i++)
   {
      if (ch[i] == 0)
      {
         answer++;
         for (int j = i; j<= n; j = j+ i)
         {
            ch[j] = 1;
         }
      }
   }
   
   return answer;
}

👾 : 에라토스트네스 체란 우선 배열을 사용하는 방법인데 배열을 주어진 n+1개(n도 포함되어야 하기 때문)  만큼 만들어서 모두 0으로 초기화된 배열을 for문을 돌다가 ch[i] == 0이면 answer++하는 방식이다. answer에 1 더한 다음, for문을 하나 더 만들어서 ch[i] == 0 이었던 i의 배수 값에 해당하는 배열에는 모두 1로 초기화해줬다. (i의 배수는 소수가 아니기 때문) 

 

이렇게 하면 시간 제한 걸리지 않고 문제를 풀 수 있다.