백준 1978번 소수 찾기 자바 Java (☆공부 243일차)

1978 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

 

 

 

---

백준 1978번 문제 소수 찾기

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	162146	75808	60564	46.614%

문제

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

입력

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

출력

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

제한

 

예제 입력 1

4
1 3 5 7

예제 출력 1

3

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/48

백준 1978번 소수 찾기 / 백준 단계별로 풀어보기 8단계 / 8. 기본 수학 2

 

무려 반년 전에 풀었던 문제

 

https://gimbalja.tistory.com/412

에라토스테네스의 체

 

이 포스팅에 소수 구하는 알고리즘인 에라토스테네스의 체 구현 방법에 대해 정리해놓았다

이 문제에선 체로 거르는 방법보다는 소수의 대칭성을 활용하긴 하지만

그 원리를 저 포스팅에 적어두었기 때문에 올린다.

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        int count = 0;
        
        for(int i = 0; i < n; i++) {
            boolean prime = true;    // 소수면 true
            int num = Integer.parseInt(st.nextToken());
        
            if(num == 1) {
                continue;
            }
            
            for(int j = 2; j <= Math.sqrt(num); j++) {    // ★★등호
                if(num % j == 0) {    // ★ 나누어 떨어지는 수가 있다면
                    prime = false;    // 소수 아님
                    break;
                }
            }
            if(prime) {
                count++;
            }
        }
        
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

 

 

---

반복문에서 등호 조건을 빼는 바람에 앞에서 두 개 틀렸다..

6개월 전엔 스캐너를 사용해서 확실히 메모리와 속도 차이가 있다

 

이땐 진짜 뭣도 모르고 그냥 받아적었구나 싶다