[JAVA] 소수 찾기

문제설명

문제 설명

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

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

 

제한 조건

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

---

입출력 예

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

코드 설명

저는 이 문제를 풀기 위해 에라토스테네스의 체라는 개념을 활용하였습니다.

먼저 이 풀이 설명을 보시기 전에 에라토스테네스 체 정리글을 한 번 읽고 와주세요!!!

int sieve[] = new int[n+1];
int cnt = 0;

• 크기가 n+1인 배열 sieve를 생성하고 모든 원소를 0으로 초기화합니다. (sieve[i] = 0은 i가 소수라는 의미입니다.)

for(int i = 2; i <= n; i++){
	if(sieve[i] == 1) continue;
		for (int j = 2*i; j<=n; j+=i){
			sieve[j] = 1; 
        }
}

• 2부터 n까지 반복문을 돌면서 현재 수 i가 이미 제외되지 않았다면 (sieve[i] == 0), i의 배수들을 전부 제외시킵니다. 
• 이를 위해 sieve[j] = 1로 표시합니다. (j = 2*i부터 시작하여 i씩 증가합니다)
• 모든 수에 대해 위의 과정을 반복합니다.

for(int i = 2; i <= n; i++){
	if(sieve[i] == 0) cnt++;
}

• sieve 배열에서 값이 0인 인덱스들을 카운트하여 소수 개수(cnt)를 계산합니다.

return cnt;

• 소수 개수(cnt)를 반환합니다.

---

소스코드&결과

소스코드

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

결과

---