[프로그래머스][JAVA]Level 1 : 소수 찾기

문제 설명

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

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

 

 

제한 조건

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

입출력 예

 

10	4
5	3

 

 

 

---

전에 배웠던 '에라토스테네스 체'를 이용했다.

배열 arr를 동적할당( 배열엔 현재 값이 0으로 초기화 )

첫 소수인 2부터 반복문 시작해서, 인덱스 값이 0이면 소수 count

그리고 해당하는 소수의 배수들의 인덱스 값을 1로 변경( 그렇게 되면 이후에 arr[i]==0이 아니니 no count )

 

* 처음에 생각을 이상하게해서 .. int[] arr=new int[n]; 이렇게 배열을 생성했더니

index가 0부터 시작이니 저렇게하면 n-1 수 까지만 판별해서 n을 판별못함

그래서 n+1...

---

 

 

import java.util.*;

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