[ Algorithm ] 백준 1978번 : 소수 찾기 - [JAVA]

🎆백준 1978번 소수 찾기🎆

---

📌문제

🔍문제 설명

문제 링크 : https://www.acmicpc.net/problem/1978

🔍예제 입력

4
1 3 5 7

🔍예제 출력

3

---

📌풀이

🔍풀이 설명

수학적 사고를 이용한 문제였다.
소수인 수의 개수를 구하는 문제였는데 (소수: 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수) 풀이 방식이 다양했지만 나는 가장 먼저 떠오른 제곱근을 이용한 풀이를 선택하였다.

1. 제곱근을 이용한 풀이
   n이 소수이기 위해서는 n의 제곱근보다 크지 않는 어떤 수로도 나눠지지 않아야 한다.

그 이후 찾아본... 에라토스테네스의 체를 이용한 풀이 방식..! 결국 코드로도 직접 짜봤다!

2. 에라토스테네스의 체를 이용한 풀이
   에라토스테네스의 체: "소수가 되는 수의 배수를 지우면 남은 건 소수가 된다"라고 생각하는 알고리즘이다. 소수가 무엇인지 찾을 필요가 없으며 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.(현재 지워지지 않은 수 x 를 중심으로 x를 제외한 x의 배수들은 모두 소수가 아니므로 배열에서 지운다.)

🔍코드

1. 제곱근 이용

package Math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//소수찾기
//제곱근 이용
public class p1978 {
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int count=0;

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

        for (int i=0; i<N; i++){
            boolean b = true;
            int n = Integer.parseInt(st.nextToken());
            if(n<2){
                //1은 소수가 아님!
                b = false;
            }
            for(int j=2; j<=Math.sqrt(n); j++){
                if(n%j==0){
                    b = false;
                }
            }
            if(b){
                count++;
            }
        }

        System.out.print(count);
    }
}

2. 에라토스테네스의 체 이용

package Math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//에라토스테네스의 체 이용방법
public class p1978 {
    static boolean number [] = new boolean[1001]; //boolean은 false로 초기화됨
    static void E (int n){
        //n을 제외한 배수를 지운다.
        int length = 1000/n;
        for(int i=2; i<=length; i++){
            number[n*i]= true;
        }
    }
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int count=0;

        number[0] = true;
        number[1] = true;

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

        for (int i = 2; i <= 1000; i++) {
            if (!number[i]) {
                E(i);
            }
        }

        for (int i=0; i<N; i++){
            int n = Integer.parseInt(st.nextToken());
            if(!number[n]){
                count++;
            }
        }

        System.out.print(count);
    }
}

---

👋마무리👋

제곱근으로 풀이한 후에 소수 찾는 알고리즘을 검색해보니 에라토스테네스의 체를 이용한 풀이가 많이 나왔다.. 다시 풀어보는 도중... boolean배열은 false로 초기화 되는 것 까먹고 계속..아하핫.. 그래도 디버깅 해서 바로 찾아내서 다행이당..>< 여러가지 방법(2개지만..ㅎ)으로 풀어본 건 첨이당 🤓