프로그래머스 소수 찾기 풀이

사이트 : 프로그래머스(Programmers) 

문제명 : 소수 찾기

 

특정 값을 받으면 1부터 받은 값 사이에 소수가 몇개나 있나 확인하는 문제인데

정직하게 모든 숫자를 다 나눠본 다음

1과 자기 자신의 경우만 나눠지는 숫자의 갯수를 더하면서 하면

 

문제는 맞아도 효율성에서 틀려서 눈물을 쏟게 된다

 

소수를 구할 때에는 에라토스테네스의 체를 써야된다고 하는데

에라토스테네스의 체란?

 

n값까지 구하면서 소수를 찾으면 소수의 배수를 구한다음

그 배수를 다 지워버리고 나면

소수만 남는다는 얘기다

 

즉 위 스크린샷에서는 120전에 소수가 몇개인지 구하는건데

11*11은 120을 넘어가기 때문에

11 전의 소수를 구한다음 그 배수를 다 빼버리면

남은 값은 다 소수라는 얘기다

 

내 풀이방법은 다음과 같은데

 

먼저 배열을 실제 받을 값보다 1 크게 만들어주는데

실제 값과 배열 번호를 동일화시키려고 한 거다

 

이후 2부터 n값을 모두 배열에 담아준다

 

이후 에라토스테네스의 체를 돌려주면 되는데

i*i가 n을 넘어서는 순간 의미가 없으므로

 

그 전에서만 소수를 계속 구해주면서

소수가 나오면 소수를 n보다 커지기 전까지 계속 곱하면서

배열의 값을 0으로 만든다

 

그리고 for를 계속 돌리면서 0으로 바뀌었을 경우에는 바로 패스해주면 된다

 

for를 다 돌린 후 배열에는 0과 0이 아닌 값만 있을텐데

0이면 소수가 아니므로 0이 아닌 값만 더해준 다음 반환하면 된다

 

마지막으로 소수 찾기에 바로 복사 붙여넣기 하면 되는 답안은 다음과 같다

import java.util.HashSet;

class Solution {
  public int solution(int n) {
	      int answer = 0;
	      int[] arr = new int[n+1];
	      
	      for(int i = 2; i<=n; i++) {
	    	  arr[i] = i;
	      }
	      
	      for(int i = 2; i*i<=n; i++) {
	    	  int multiplier = 2;
	    	  if(arr[i] == 0) {
	    		  continue;
	    	  }

	    	  for(int j = i; j<=n;) {
				  if(j * multiplier > n) {
					  break;
			  	  }
				  arr[j*multiplier] = 0;
				  multiplier++;
	    	  }
	      }
	      
	      for(int i = 1; i<arr.length; i++) {
	    	  if(arr[i] != 0) {
	    		  answer++;
	    	  }
	      }
	      return answer;
  }
}