[Inflearn] 자바 알고리즘 문제풀이 #02-05 5. 소수(에라토스테네스 체)

문제

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력 

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력 

첫 줄에 소수의 개수를 출력합니다.

 

 

 

내 풀이

import java.util.Scanner;

public class Main2_5 {
    public int Solution(int n) {
        int answer=0;
        for (int i = 2; i <= n; i++) { // 2부터 n까지 반복
            int cnt = 0;
            for (int j = 1; j <= i; j++) {
                if(i%j==0) cnt++; // 나눠 떨어지면 cnt 증가
            }
            if(cnt==2) answer++; // cnt가 2개(1과 자기 자신)일 경우 소수
        }
        return answer;
    }

    public static void main(String[] args) {
        Main2_5 T = new Main2_5();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println(T.Solution(num));
    }
}

이중 for문으로 푸는 방법밖에 생각이 안나서 구현했더니 결과는 Time Limit Exceeded....

1902ms나 걸림....ㅎ 빠르게 선생님 풀이 참고했다 ^^

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main2_5 {
    public int Solution(int n) {
        int answer=0;
        int[] ch = new int[n+1]; // 인덱스 n까지의 배열을 생성하기 위해
        for (int i = 2; i <= n; i++) {
            if(ch[i]==0) {
                answer++;
                for (int j = i; j <= n; j=j+i) ch[j] = 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main2_5 T = new Main2_5();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println(T.Solution(num));
    }
}

오우... 어떻게 하면 배열에 0, 1 flag값을 가지고 간단히 구현하는 생각을 할 수 있을까 큐ㅠㅠ

해당 인덱스 값이 0인지 확인한 후 0이면 answer++하고 그 배수들은 모두 막아버리는 멋진 풀이...

이중 for문이어도 구현이 간단하면 시간초과 안걸리는구나.... 명심....!

 

 

 

결과