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

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

1978번: 소수 찾기

---

---

주의점

소수

• 1과 자기 자신만을 약수로 가지는 자연수
• 1은 소수가 아님 ➡ 예외 처리 필수
• 해당 범위 : 2 ~ (N - 1)

---

알고리즘 : 소수 찾기

1. 기본 판별법

• 1과 자기 자신만을 약수로 가짐 ➡ 2부터 판별하려는 수 직전까지 하나씩 나누기

나눠 떨어지는 수 有	소수 O
나눠 떨어지는 수 無	소수 X

---

2. 제곱근 판별법

• Number = A X B 의 합성수 (Number = A X B)
• 1 ≤ A, B ≤ Number

 

• 만약 A와 B가 Number의 제곱근보다 커지면 모순 발생

A, B > sqrt(Number)
A X B > Number
A X B != Number

∴ A X B = Number 에서 A와 B 중 적어도 하나는 Number의 제곱근보다 작거나 같다.

 

• Number의 제곱근 이상의 수로 Number 나눌 경우

Number = 12
12의 약수 = 1, 2, 3, 4, 6, 12
√12 ≒ 3.46

12를 4 이상부터 검사하면
12 ÷ 4 = 3 ... 0 ➡ 약수
12 ÷ 5 = 2 ... 2 ➡ 약수 X
12 ÷ 6 = 1 ... 0 ➡ 약수
12 ÷ 7 = 1 ... 5 ➡ 약수 X
12 ÷ 8 = 1 ... 4 ➡ 약수 X
12 ÷ 9 = 1 ... 3 ➡ 약수 X
12 ÷ 10 = 1 ... 2 ➡ 약수 X
12 ÷ 11 = 1 ... 1 ➡ 약수 X

Number 제급근 이상의 수로 Number 나누면 두 가지 경우만 발생함
1. 이전에 검사한 수 중 약수인 수를 약수로 가짐
2. 약수가 아님
∴ 소수 판별 시 Number - 1 까지 가지 않고, Number의 제곱근 범위까지만 검사하면 됨

---

3. 에라토스테네스의 체

• 가장 대표적인 방법 중 하나
• 여러 개의 소수를 체를 거르듯 구하기
• 2를 제외한 2의 배수 모두 거르기 ... 3을 제외한 3의 배수 모두 거르기 ... (반복)
• 이 또한 2번 방법처럼 구하려는 범위의 최대값의 제곱근까지만 반복하면 됨

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

---

풀이

1. Scanner

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
		
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int count = 0;
		
        for(int i = 0; i < N; i++) {
            //소수 O = true, 소수 X = false
            boolean isPrime = true;
            
            int num = in.nextInt();
            if(num == 1) { //1이면 다시 반복문으로(예외 처리)
                continue;
            }
            
            for(int j = 2; j <= Math.sqrt(num); j++) {
                if(num % j == 0) {
                    isPrime = false; //소수 X = false
                    break;
                }
            }
            if(isPrime) { //소수 O ➡ count + 1
                count++;
            }
        }
        System.out.println(count);
    }
}

 

2. BufferedReader

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
		
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //변수 N : StringTokenizer의 hasMoreTokens() 사용 시 필요 없음
        br.readLine();
        int count = 0;
		
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
        //hasMoreTokens(): StringTokenizer에 토큰이 남아있는지 여부를 true/false로 반환
        while(st.hasMoreTokens()) {
            //소수 O = true, 소수 X = false
            boolean isPrime = true;
			
            int num = Integer.parseInt(st.nextToken());
            if(num == 1) {
                continue;
            }
            
            for(int i = 2; i <= Math.sqrt(num); i++) {
                if(num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            
            if(isPrime) {
                count++;
            }
        }
        System.out.println(count);
    }
}

---

성능

• BufferedReader > Scanner
• 에라토스테네스의 체 > 제곱근 판별 > 기본 판별

 

---

출처 : https://st-lab.tistory.com/80