5. 소수(에라토스테네스의 체)

1. 문제

입력 n 이하의 소수 개수를 구하시오.

 

2. 나의 풀이

코드는 작성 했으나 시간초과로 오답 판정.

내 머리로는 1부터 자기자신으로 나누는 노가다 반복문 말고는 다른 방법이 안떠올라 강의를 봤다.

 

3 - 1. 강의 풀이

강의에서는 에라토스테네스의 체에 대해 설명한다.

출처: 위키 백과

 

 

3 - 2. 강의 코드

package Algorythm_Array;

import java.util.Scanner;

public class Array05 {
    public static int solution(int n) {
        int answer=0;
        int[] intArr = new int[n + 1];
        for (int i = 2; i <= n; i++) {
        	//int 배열의 기본 초기화값은 0 이므로 intArr[2]도 0
            if(intArr[i]==0){
                answer++;
                //i 이후 부분을 모두 1로 칠해서 소수가 아님을 표시한다.
                for (int j = i; j <= n; j=j+i) {
                    intArr[j]=1;
                }
            }

        }

        return answer;

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));

    }
}

 

4. 얻어갈 점

수학적으로 명료하면서 깔끔한 알고리즘 하나 배워간다.

코드는 더 자세하게 공부해보자