(1일 1코딩)프로그래머스 소수 찾기[JAVA]

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

코딩테스트 연습 - 소수 찾기

 

오늘의 코드 리뷰는 프로그래머스 소수 찾기

 

1부터 입력받은 숫자 사이에 소수의 개수가 몇개인지 반환하는 문제

 

import java.util.*;

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

이 문제도 인프런 알고리즘 인강을 참고해서 풀었습니다!

 

에라토스테네스체를 사용해서 소수 파악했어요

 

2부터 시작해서 (1은 소수가 아니니까용!) 2의 배수의 배열에 1을 채워주고 3의배수 5의배수...모두 동일하게 방을 1로 채워서 방에 0이 있었던 경우만 소수로 체크해서 풀었네요