[알고리즘] 소수찾기(백준1978번)

---

keyword : 소수
difficulty : 하
completion : ✅
notice :

---

소수찾기

📝 문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

---

🔍 정답

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  

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());  
        ArrayList<Integer> array = new ArrayList<>();  

        StringTokenizer st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < N; i++) {  
            while (st.hasMoreTokens()) {  
                array.add(Integer.parseInt(st.nextToken()));  
            }  
        }  

        ArrayList<Integer> result = new ArrayList<>();  
        for (int i = 0; i < array.size(); i++) {  
            result.add(prime(array.get(i)));  
        }  

        int size = result.size();  
        int cnt = 0;  
        for (int i = 0; i < result.size(); i++) {  
            if (result.get(i).equals(0)) cnt++;  
        }  
        System.out.println(size - cnt);  
    }  

    public static int prime(int num) {  
        if (num == 1) return 0;  
        for (int i = 2; i < num; i++) {  
            if (num % i == 0) {  
                return 0;  
            } else continue;  
        }  
        return num;  
    }  
}

• 소수는 1과 자기 자신으로만 나누어떨어지는 수인데, 그렇다면 1과 자기 자신 외에 어떠한 숫자로 나누었을 때 나머지가 0인 경우는 소수가 아닌 것이다. (prime 메소드의 for문을 2부터 자기자신보다 1 작은 범위로 둔 이유)
• 우선, array 배열에 입력값을 모두 넣는다.
  • 예시) array = [1, 2, 4, 6, 7]
• result라는 새로운 배열을 만들고, array배열의 인덱스를 하나하나 꺼내어서 prime 메소드를 거친다
  • prime 메소드는 2부터 자기자신-1의 범위로 숫자를 하나하나씩 대입하여 나누어보다가 나머지가 0인 경우가 생기면(1과 자기자신 외 다른 숫자로 나누어지는 경우이므로 소수가 아닌 경우임) 0을 리턴한다.
  • 만약 나머지가 0이 아니면 계속 continue를 하다가 자기 자신을 리턴한다.
  • 1은 소수가 아니므로 0을 리턴하게 하였다.(이 부분은 좀 더 깔끔하게 하는 방법이 있을 것 같은데 ㅠㅠㅠ)
  • 예시) array = [1, 2, 4, 6, 7] -> result = [0, 2, 0, 0, 7]
• result 배열을 for문으로 돌다가 0이 나오면 cnt를 하나씩 늘려준다.
• result 배열의 크기에서 cnt(소수가 아닌 수들)를 빼주면 소수의 개수만 남는다.