[Programmers] 소수 찾기 -JAVA

📄 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

📑 제한 조건

• n은 2이상 1000000이하의 자연수입니다.

📇 입출력 예

n	result
10	4
5	3

👨🏻‍💻 내가 작성한 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
	for(int i = 2; i <= n; i++) {
	   boolean prime = false;// 소수 
	    for(int j = 2; j < i; j++) {
	    		 if(i % j == 0) {
	    			 prime = true;
	    			 break;
	    		 }
	    	 }
	    	 if(!prime) {
	    		 answer++;
	    	 }
	     }
	     
	     return answer;
    }
}

결과

🤷🏻‍♂️..? 뭐지..?😭 찾아보니 n의 크기가 작으면 for 문이 돌아가는 횟수가 적기 때문에 테스트에는 문제가 없지만 n=1000000이라면 2~1000000까지 하나하나 다 비교를 하기엔 효율성이 너무 안 좋다..! 그래서 사용한 알고리즘이 "에라토스 테네스의 체"이다.

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 마치 체로 치듯이 수를 걸러낸다고 하여 "에라스토테네스의 체"라고 부른다.

👨🏻‍💻 다시 작성한 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
	     int[] numbers = new int[n+1];
	     
	     for(int i=2; i<=n; i++) {
	    	 numbers[i] = i;
	     }
	      for(int i=2; i<n; i++) {
	    	 
	         if(numbers[i] == 0) { 
	        	 continue;
	         }	
	         for(int j=2*i; j<=n; j+=i) {
	        	 numbers[j] = 0;
	         }
	       }
	  
	       for(int i=0; i<numbers.length; i++) {
	  
	         if(numbers[i] != 0) answer++;
	       }
	  
	     return answer;
    }
}

👨🏻‍🏫 코드 풀이

소수란
1과 자기 자신만을 약수로 가지는 수다

• 처음 for문에서 2부터 배열에 넣어준 이유는 소수가 2부터 시작하기 때문이다.

• 두번째 for문에서 부터 에라토스테네스의 체를 사용한다.

  • for(int j=2*i; j<=n; j+=i) 소수의 배수는 제거해준다(값을 0으로 바꿔줌)
  • if(numbers[i] == 0) 값이 0이라면 소수가 아니라 continue를 해준다.

결과

👍🏻