[BOJ 1978] 소수 찾기

-> 문제 바로가기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	260961	124865	99860	47.534%

문제

---

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

입력

---

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

출력

---

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

예제

---

// 입력
4
1 3 5 7

// 출력
3

출처

---

• 문제의 오타를 찾은 사람: djm03178
• 데이터를 추가한 사람: bclim9108, nova9128

알고리즘 분류

---

• 수학
• 정수론
• 소수 판정

제출

---

내 제출

---

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

public class Main {

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        br.readLine();	// N 은 쓰지 않음.
        int count = 0;

        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        while(st.hasMoreTokens()) {

            // 소수인경우 true, 아닌경우 false
            boolean isPrime = true;

            int num = Integer.parseInt(st.nextToken());

            if(num == 1) {
                continue;
            }
            for(int i = 2; i <= Math.sqrt(num); i++) { // 제곱근을 이용한 방법
                if(num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                count++;
            }
        }
        System.out.println(count);
    }
    // 참조 : https://st-lab.tistory.com/80


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

런타임	메모리
104 ms	14192 KB

Reference

---