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

🔺 문제

1978번: 소수 찾기

 

🔺 코드

-  방법1)

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

public class Main {
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		int cnt = 0;
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0 ; i < n ; i++) {
		    arr[i] = Integer.parseInt(st.nextToken());
		    
		    boolean flag = true;
		    
		    if(arr[i] == 1) flag = false;
		    
		    for(int j = 2 ; j <= Math.sqrt(arr[i]) ; j++) {
		        if(arr[i] % j == 0) {
		            flag = false;
		            break;
		        }
		    }
		    
		    if(flag) cnt++;
		}
		
		System.out.println(cnt);
	}
}

✅ 해결 아이디어
- 소수 여부를 boolean으로 표시 → 소수이면 true / 소수가 아니면 false로
- 입력받은 값이 1이라면, 소수가 아니게 처리 (20번째 줄)

 

- 방법2) 에라토스테네스의 체 이용

import java.util.*;
import java.io.*;
 
public class Main {
    public static final int MAX = 1001;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 에라토스테네스의 체
        boolean[] isPrime = new boolean[MAX];
        for(int i = 2 ; i < MAX ; i++) {
            isPrime[i] = true;
        }
    
        for(int i = 2 ; i <= Math.sqrt(MAX) ; i++) {
            for(int j = i * i ; j < MAX ; j += i) {
                if(!isPrime[j]) continue;
                isPrime[j] = false;
            }
        }
 
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < n ; i++) {
            int x = Integer.parseInt(st.nextToken());
            if(isPrime[x]) cnt++;
        }
        
        System.out.println(cnt);
    }
}

---

🔺 다른 풀이들

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

여러가지 풀이 방법... 그 중에서도 에라토스테네스의 체를 사용한 코드가 있음!

---

(참고)

✔ 프로그래머스 - 소수 찾기

[프로그래머스/Lv. 1] 소수 찾기

 

✔ 에라토스테네스의 체

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)

 

[백준 1978] 소수 찾기

---

(+ 6/12 2회독)

계속 풀고 계속 틀리는 에라토스테네스의 체ㅎ

본체만체 하고 싶다

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX  = 1001;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        boolean[] isPrime = new boolean[MAX];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for(int i = 2 ; i <= Math.sqrt(MAX) ; i++) {
            if(!isPrime[i]) continue;    // 이미 체크된 배열이면 skip
            
            for(int j = i * i ; j < MAX ; j += i) {
                isPrime[j] = false;
            }
        }
        
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        while(n --> 0) {
            int x = Integer.parseInt(st.nextToken());
            if(isPrime[x]) cnt++;
        }
        
        System.out.println(cnt);
    }
}