[JAVA-자바] 1978번: 소수 찾기

 

문제에서 말하는 "소수"는 무엇인가 ?

소수의 정의는 '1과 자기 자신으로밖에 나누어 떨어지지 않고 자기 자신의 곱셈의 역수가 없는 수'이다.
쉽게 이해하기 위해 소수를 '약수가 2개인 수'로 정의하기도 한다.
참고로 1은 1과 자기 자신(1)으로만 나눠떨어지긴 하지만, 곱셈의 역수가 있는 1을 소수로 인정하면 소인수분해의 유일성이 사라지는 등의 문제로 인해 1은 소수가 아닌 것으로 약속했다.
따라서 1은 자연수이지만 소수도 아니고 합성수도 아니다.

출처: 나무위키

 

1부터 10까지의 수 중 소수를 꼽아보자면

2, 3, 5, 7 이렇게 4개만이 소수이기 때문에, 예제에서 1 3 5 7를 입력했을때, 결과가 3이 나오는 것이다.

 

자 그럼 이제 소수가 무엇인지 알았으니, 어떻게 소수인지 구별할 수 있을까요?

 

우선 우리가 판별하고자 하는 수를 N이라고 정의하고,

2부터 N - 1 까지의 수로 하나하나 나눠보고 만약 나뉜다면 그 수는 소수가 아니고, 나눠지지 않는다면 소수입니다.

이걸 메서드화 시켜보자면 다음과 같습니다  

 

소수인지 판별하는 메서드:

public static boolean isPrimeNumber(final int number) {
    if (number <= 1) {
        return false;
    }

    for (int i = 2; i <= (number - 1); i++) {
        if (number % i == 0) {
            return false;
        }
    }

    return true;
}

 

이제 소수를 판별하는 isPrimeNumber메서드가 생겼으니, Main함수에서 잘 사용해줍시다.

 

소스코드:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int count = 0;
    int N = sc.nextInt();

    for (int i = 0; i < N; i++) {
        int number = sc.nextInt();
        if (isPrimeNumber(number)) {
            count++;
        }
    }

    sc.close();

    System.out.println(count);
}

 

시간복잡도&최적화 관련은 연관된 다른 문제에서 다루도록 하겠습니다!

 

 

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.