[소수] 프로그래머스 level1 소수찾기 자바(java) 풀이

프로그래머스 소수 찾기 자바(java) 풀이

• Level 1
• 소수 찾기
  
  
  

문제 정리

1. N이 주어질떄 1이상 N이하의 수중 소수의 개수를 구하여라
   
   
   

문제 풀이(solution)

소수의 정의와 간단한 최적화만 해준다면 풀 수 있습니다.

1. 어떤수 N이 1과 자기 자신외에 다른 수로 나누어떨어진다면 그 수는 소수가 아닙니다.
2. 즉 1부터 N사이의 수를 모두 2이상 자기이하의 수로 나누어 봅니다.
   그래서 나누어떨어지는 수가 하나라도 있다면 그 수는 소수가 아닙니다.
   하나도 없다면 그 수는 소수가 됩니다.
3. 하지만 2번 처럼 그 수 전까지 모두 나누어 보면 시간초과가 발생합니다. 그래서 루트 N까지로만 나누어 보면 됩니다.
   예를 들어 10이 소수인지 아닌지 구한다면 2부터 루트10 까지의 수로만 나누어 보면 알 수 있습니다.
   
   
   

에라토스 테네스의 체 이용(solution2)

에라토스 테네스의 체를 이용하여 훨씬 빠른 시간안에 소수의 개수를 구할 수 있습니다.

1. boolean 배열을 이용한다.
2. n이하의 수까지 모두 탐색한다
3. i번째를 탐색했는데 false라면 그 수는 소수이다. 이를 list에 넣는다
4. 소수의 배수들을 n보다 작은 선에서 모두 true로 체크한다.
   예를 들어 처음에 2를 확인. 2는 소수로 체크
   2의 배수를 모두 소수가 아닌수(true)로 체크
5. 다음으로 false인 수를 찾는다 그 수가 소수가 된다.
6. 위의 과정을 계속해서 반복하면 list에는 소수만 담기게 된다.
7. list의 크기를 구하면 1~n 사이의 소수의 개수가 된다.
   
   
   

프로그래머스 소수 찾기 자바(java) 두 가지 풀이

import java.util.*;
class Solution {
    public static void main(String[] args){
        int n = 10;
        int n2 = 5;
        System.out.println(solution2(n));
        System.out.println(solution2(n2));
    }

    public static int solution(int n) {
        // 1~N 사이의 소수의 개수
        // N은 1000000이하
        int ans = 0;
        boolean flag;
        for(int i=2; i<=n; i++){
            flag = true;
            for(int j=2; j<=Math.sqrt(i); j++){
                if(i % j == 0){
                    flag = false;
                    break;   
                }
            }
            if(flag)
                ans++;
        }
        return ans;
    }

    public static int solution2(int n) {
        // 에라토스테네스의 체 이용
        boolean[] era = new boolean[n+1];
        ArrayList<Integer> list = new ArrayList<>();    // 소수를 담을 list

        for(int i=2; i<=n; i++){
            if(!era[i]){
                list.add(i);
                for(int j=1; i*j<=n; j++)
                    era[i*j] = true;
            }
        }

        return list.size();
    }
}