프로그래머스-level1-소수 찾기(에라토스테네스의 체)

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

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

소수찾기 문제이다.(자신과 1만 약수로 가지는 수)

 

정보처리기사에서 공부하던 문제이기에 별 문제 아니라 생각하고 풀었다. 

 

뭐 나름 깔끔한 코드라고 생각했는데 효율성에서 통과를 못했다.(시간 초과)

 

고민하다가 예전에 에라토스테네스의 체라는게 기억이 나서 검색을 해봤다. 일단 밑에는 효율성 낮은 코드(돌아감)

public int solution(int n) {
	      int count = 1;
	      if(n == 2) {
	    	  return count;
	      }
	      
	      for (int i = 3; i<= n; i++) {
	    	  for(int j = 2; j <= i-1; j++) {
	    		  if(i%j==0) {
	    			  break;
	    		  }
	    		  if(j == i-1) {
	    			  System.out.print(j+1 + " ");
	    			  count++;
	    		  }
	    	  }
	      }
	      return count; 
}

에라토스테네스의 체라는건 1을 먼저 제외하고, 2부터 시작해서 2의 배수, 3의 배수, 5의 배수, 7의 배수, 소수들의 제곱근을 제거하면 남은 수들이 소수의 집합들이다.

 public int solution(int n) {
		 int[] a = new int[n+1];
		 for(int i = 2; i <= n; i++) {
			 a[i] = i;
		 }
		 for(int i = 2; i <= n; i++) {
			 if(a[i] == 0) continue;
			 for(int j = i + i; j <= n; j+= i) {
				 a[j] = 0;
			 }
		 }
		 int count = 0;
		 for(int i = 2; i <= n; i++) {
			 if(a[i] != 0) count++;
		 }
		 return count;
}

해당 코드

결과를 보면 알겠지만 굉장히 빠른편이다.

 

에라토스테네스의 체에 대한 자세한 설명은

https://terms.naver.com/entry.nhn?cid=40942&docId=1179083&categoryId=32204

에라토스테네스의 체

참고하면 된다.