[Programmers]소수 찾기_자바 / 프로그래머스 연습문제(level 1)

https://programmers.co.kr/learn/courses/30/lessons/12921?language=java 

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

 

1부터 주어진 숫자 사이이 소수의 갯수를 찾는 문제입니다.

단, 1은 소수가 아니라고 문제에서 주어졌기 때문에(실제로도 소수가 아닙니다) 반복문을 돌릴떄 2부터 돌렸습니다!

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++) {
            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;
    }

}

우선 numbers라는 배열을 만들었네요! 배열의 길이는 n+1만큼 주었습니다.

그리고 소수가 아닌수자는 배열에서 모두 0이라고 대입해줄 예정입니다.

2를 제외한 짝수는 모두 소수가 아닙니다. 그래서 모두 0을 대입해줬습니다.

같은 방식으로 소수가 아닌 숫자들을 찾아서 0을 대입합니다.

이후 배열에서 0이 아닌것들의 갯수를 세어주면 소수의 갯수가 출력이됩니다.