프로그래머스[Java] - 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기 | 프로그래머스

코드

class Solution {
	  public int solution(int n) {
	      int answer = 1;
          for(int i=3; i<=n; i++){
              boolean flag = true;
              for(int j=2; j<=Math.sqrt(i); j++){
                  if(i%j == 0){
                      flag = false;
                      break;
                  }
              }
              if(flag)      answer ++;
          }
	      return answer;
	  }
	}

풀이

 

기본적인 소수 찾기 코드.

2 ~ i의 제곱근까지 반복하며 나누어 떨어지면 소수 X

 

 

코드

class Solution {
	  public int solution(int n) {
	      int answer = 0;
          boolean[] check = new boolean[n+1];
          check[0] = check[1] = false;
          
          for(int i=2; i<=n; i++)    check[i] = true;
          
          // i의 배수들 전부 거르기(소수가 아니므로)
          for(int i=2; i<=Math.sqrt(n); i++){
              if(!check[i])     continue;   // 이미 걸러진 수의 배수 - pass
              for(int j=2; i*j<=n; j++)  check[i*j] = false;
          }
          
          for(int i=2; i<=n; i++)
              if(check[i])  answer ++;
	      return answer;
	  }
	}

풀이

에라토스테네스의 체를 사용한 소수 찾기.

i의 배수들은 전부 거른 후 판별.

자세한 풀이 - 참고

 

기본적인 소수 찾기 코드

 

에라토스테네스의 체 소수 찾기 코드

효율성 테스트에서 거의 10배가량 차이가 난다.