[프로그래머스 / 소수 찾기 / JAVA]

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

프로그래머스

 

문제 접근

단순한 문제 설명에 비해 시간 제한이 붙은 문제라 처음에 모든 수를 일일이 찾으니 시간 제한에 잡혔다.

소수 찾기는 풀 때 마다 새로운 기분이다..

 

힌트를 찾아보면 에라토스테네스의 체에 대한 얘기가 많다.

간략히 하면 2부터 해당 숫자의 제곱근까지 탐색하면서 소수들의 배수들을 삭제하고 나면 남은 숫자들이 소수란 소리다.

* 2, 3은 소수라 시작부터 2와 3의 배열들은 삭제

 

자세한 설명 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

정해진 숫자의 크기+1만큼의 정수 배열에 각 공간에 순서에 맞는 값 대입

이후 제곱근 까지의 반복문을 돌면서 소수의 배수들은 값을 0으로 지정

처음에 2와 3은 소수기에 2번만 돌아도 상당 수의 2, 3배수들이 0으로 됨

이러면 소수인 수들은 0이 아닌 값을 가지기에 갯수를 세주면 된다.

class Solution {
   public int solution(int n) {
  
		 int[] num = new int[n+1];
		 
		 for(int i=0; i<=n; i++) num[i] = i;
		  int answer = 0;  
		  
		 // 제곱근보다 작은 소수들의 배수들을 지워주고 남은 수 들이 소수
	     // 배열의 값들이 0이면 소수 X, 0이 아니면 소수
  
		  for(int i=2; i<=Math.sqrt(n); i++) {
	         if(num[i] == 0) continue; // 소수의 배수들은 0으로 처리했기에 0이면 바로 다음 수 작업
	         
	         // 소수의 배수들을 처리 작업
	         for(int j=i*2; j<=n; j += i) num[j] = 0;
		  }
		  
		  num[1] = 0; // 1은 계산할 필요없으니 0 박아놓음
		  for(int i : num) if(i != 0) answer++;

		  return answer;
	    }
}

 

처음엔 에라토스뭐시기고 이해가 안되더라..