[백준, 자바] 1978번 - 소수 찾기

소수 찾기

주어진 숫자 배열에서 소수의 개수를 출력하기.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String[] numbers = br.readLine().split(" ");
        int count = 0;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(numbers[i]);
            if(isPrimeNumber(num)) count++;
        }

        System.out.println(count);

    }

    public static boolean isPrimeNumber(int num) {
        // 1 이하는 전부 소수 아님, 2,3은 소수이지만 2의 배수는 소수가 아님, 
        if (num <= 1) return false;    // 1은 소수가 아니다.
        if (num <= 3) return true;    // 2와3은 소수이다.
        if (num % 2 ==0) return false;
        for(int div = 3; div <= Math.sqrt(num); div+=2) {
            if(num % div == 0) {
                return false;
            }
        }
        return true;
    }
}

아래는 while문을 사용한 정답니다. 출처 : 코딩팩토리

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String[] numbers = br.readLine().split(" ");
        int count = 0;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(numbers[i]);
            if(isPrimeNumber(num)) count++;
        }

        System.out.println(count);

    }

    public static boolean isPrimeNumber(int num) {
        if (num <= 1) return false;    // 1은 소수가 아니다.
        if (num <= 3) return true;    // 2와3은 소수이다.
        if (num % 2 ==0) return false;

        int divisor = 2;
        int tmp = num - 1;

       while(true) {
           if(divisor <= tmp) {
               // n - 1이 divisor보다 작거나 같을때 divisor로 나누어 떨어지면 소수가 아님.
               if(num % divisor == 0) {
                   return false;
               }else {
                   divisor++;
               }
           } else { // 위해서 return false된 경우를 제외한 나머지 경우 : 소수
               return true;
           }
        }
    }
}

결과 및 소요 시간

오답 (4일)

풀이

소수는 본인 N부터 2까지 N--해서 나누었을 때 나누어 떨어지지 않아야 한대서
num부터 --해서 2가 될 때까지 계속 % 연산을 해서 구해보았는데 오답이었다. 뭘 잘못한 것 같다.

소수를 구하려면 에라토스테네스의 체를 이용하는 방법이 있다고 한다.
근데 이건 자연수의 범위가 주어졌을 때 유용한 방법인데 이 경우에는 주어진 배열 안 수들이 연속적이지 않다. 따라서 함수를 만들어서 처리했다.

for문으로 비교를 하기 전에 먼저 1,2,3을 분기처리해서 쳐내는데 허술하게 처리를 해서 오답을 냈었다. 괜히 허술하게 하지 말자.

if (num == 1) return false;
//        if (num % 2 == 0) return false;

if (num <= 1) return false;    // 1은 소수가 아니다.
        if (num <= 3) return true;    // 2와3은 소수이다.
        if (num % 2 ==0) return false;
        for(int div = 3; div <= Math.sqrt(num); div+=2) {
            if(num % div == 0) {
                return false;
            }
        }