[049] 1978. 소수 찾기

✨ 알고리즘 분류 : 수학 / 정수론 / 소수 판정

 

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

1978번: 소수 찾기

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 주어진 개수 중에 소수의 갯수를 출력한다

- 소수는 1000 이하의 자연수이다

 

 

 

 

🧶 풀이과정 

 

처음에 문제를 반대로 이해해서 틀렸다 ^^; 반대로 이해해서 수 중 제일 큰 것이 100인 줄 알고 재귀로 만들었는데 왜 틀렸지? 하고 문제를 다시 보니까 반대로 이해했더라.

 

소수를 찾는 방법은 다음과 같다.

1. 해당하는 수의 루트값까지 하나씩 수를 올리면서 나누어본다.

+ a, b일 경우 a와 b의 값이 같아지는 순간 그 뒤는 b , a 로 이전과 동일한 계산이라 루트값까지만 계산한다

2. 나눈 값이 0이 있을 경우 소수가 아니므로 제외, 끝까지 돌고 나면 소수이다

 

이것을 반복하여 카운트를 올리면 끝!

 

 

 

🏹 제출코드

 

package data_structure_part_01;

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Q1978 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

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

        int cnt = 0;
        for(int i = 0; i < n; i++){

            int num = Integer.parseInt(st.nextToken());
            boolean ck = true;

            if(num >= 2){

                for(int j = 2; j * j <= num; j++){

                    if(num % j == 0){
                        ck = false;
                        break;
                    }
                }

                if(ck) cnt++;
            }

        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();


    }


}

 

 

문제를 제대로 읽자