Algorithm - Sieve of Eratosthenes

  • 2023-10-24 에 풀이한 문제
  • 풀이 시간 1 : 10:32 ~ 10:35 ( 타임 리미트 오답 )
  • 풀이 시간 2 : 11:35 ~ 11:41 ( 공부 후 다시 풀이 -> 정답 )


1. 에라토스테네스의 체?

  • 에라토스테네스의 체 알고리즘은, 소수를 구하는 알고리즘이다. 
      public class A {
      public static int primeNumbers_timeLimitExceeCode(int num) {
          List<Integer> iList = new ArrayList<>();
          for (int i=2; i<=num; i++) {
              int count = 0;
              for (int j=2; j<=i; j++ ) {
                  if ( i % j == 0) count ++;
                  if (count >= 2) break;
              }
              if (count == 1) iList.add(i);
          }
          return iList.size();
      }
  }
  • 우리가 소수를 구할 때 해당 코드처럼 2중 루프문을 만들면 시간 복잡도에 걸려 오답처리가 될 가능성이 크다.
  • 애초에 소수를 구하는 문제를 물어보면, 그냥 에라토스테네스의 체를 물어보는거라고 생각하면 편하다.


  • 에라토스테네스의 체는 “소수가 되는 수의 배수를 지우면 남은 건 소수가 된다” 라고 생각하면 된다.
  • 소수가 무엇인지 찾을 필요가 없으며 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.
  • 순서는 이러하다.
    • 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
    • 소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다
    • 자기 자신을 제외한 2의 배수를 모두 지운다.
    • 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
    • 자기 자신을 제외한 3의 배수를 모두 지운다.
    • 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
    • 자기 자신을 제외한 5의 배수를 모두 지운다.
    • 위 과정을 반복한다.


  • 이걸 코드로 구현하면 다음과 같다. 
      public class A {
      public static int eratosthenesSieve(int num) {

          boolean[] isPrime = new boolean[num+1];
          Arrays.fill(isPrime, true);
          isPrime[0] = isPrime[1] = false;

          for ( int i=2; i*i<=num; i++) {
              if(isPrime[i]) {
                  for ( int j=i*i; j<=num; j+=i ) {
                      isPrime[j] = false;
                  }
              }
          }

          int answer = 0;
          for ( boolean tf : isPrime ) {
              if(tf) answer++;
          }

          return answer;
      }
  }
    • isPrime 이라는 boolean 배열을 만들고, true로 채워준다.
    • 이 때 boolean이라는 배열은 우리가 찾으려하는 수보다 +1 만큼 커야한다.
    • 그 이유는 boolean[n] 에서 n을 idx 개념이 아닌 숫자 개념으로 볼 것이기 때문이다.
    • 0과 1은 소수가 아니므로 boolean[0] 과 boolean[1] 에는 false를 넣어준다.
    • 그리고 2부터 루프문을 돌려주면 된다.
    • 루프문에서 주의 할 점은 i*i <= num 까지 돌려야 한다는 것이다.
    • 이후 true의 개수를 찾아서 반환해주면, 소수의 개수를 알 수 있다.






results matching ""

    No results matching ""