[실전 문제] findprime

1. 문제

주어진 숫자들 중 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 

---

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 줄에 걸쳐 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력

4
1
3
5
7

예제 출력

3

 

 

 

2. 풀이

• 1은 소수가 아니다.
• 2 부터 자기자신 전까지의 모든 수 중, 나누어 떨어지면 소수가 아니다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 소수는 자기자신과 1로만 이루어진 수
        int count = 0;
        boolean isPrime = true;
        for(int i = 0; i < n; i++) {
            if(arr[i] == 1) continue; // 1은 소수가 아니기 때문
            for(int j = 2; j < arr[i]; j++) {
                if(arr[i] % j == 0) {
                    isPrime = false;
                    break;
                } else isPrime = true;
            }
            if(isPrime) count++;
            isPrime = true;
        }

        bw.write(count + "");
        br.close();
        bw.flush();
        bw.close();
    }
}

아래의 코드는 첫 번째 코드보다 훨씬 간결하게 구성할 수 있다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 소수는 자기자신과 1로만 이루어진 수
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 2; j <= arr[i]; j++) {
                if(arr[i] == j) count++;
                if(arr[i] % j == 0) break;
            }
        }

        bw.write(count + "");
        br.close();
        bw.flush();
        bw.close();
    }
}