소수(에라토스테네스 체)

문제 정보

• 사이트 : Infrean 자바 알고리즘 문제 풀이 강의
• 문제 번호 : 2강 5번
• 문제 분류 : Array

문제 풀이

내가 처음에 짠 코드

• 소수의 정의는 약수가 자신과 1밖에 없는 수이다.
• 그러므로 약수가 생기는 수를 boolean배열에서 true로 바꿔 제외시켜준다.
• 첫번째 for문의 범위는 2번째 for문과 곱셈을 해줄 것이므로 n의 절반으로 설정시켜준다.

import java.util.Scanner;

public class 소수_에라토스테네스_체 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        boolean[] nArr = new boolean[n+1];
        solution(n, nArr);
        for (int i = 2; i <= n; i++) {
            if(!nArr[i])
                count++;
        }
        System.out.println(count);
    }

    private static void solution(int n, boolean[] nArr) {
        for (int i = 2; i <= n/2; i++) {
            for (int j = 2; i * j <= n; j++) {
                if(!nArr[i*j])
                    nArr[i*j] = true;
            }
        }
    }
}

정답 코드

• 방식은 같고 표현하는 방법이 달랐다.

import java.util.Scanner;

public class 소수_에라토스테네스_체 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] nArr = new boolean[n+1];
        System.out.println(solution(n, nArr));
    }

    private static void solution(int n, boolean[] nArr) {
        for (int i = 2; i <= n; i++) {
            if(!nArr[i]) {
                for (int j = i; j <= n; j=j+i) {
                    nArr[i*j] = true;
                }
            }
        }
    }
}

문제 출처

Infrean 자바 알고리즘 문제 풀이

썸네일 출처

Image by storyset on Freepik