소수 찾기, 구하기

이 글에서는 백준에 있는 소수 문제들을 풀면서 배웠던 부분을 정리하려고 한다. 

소수 문제는 '에라토스테네스의 체'라는 개념만 확실히 알고 있어도 반 이상은 먹고 들어간다고 생각한다. 

 

소수?

모두가 알고 있듯이 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 

이런 소수를 찾는데 유명한 방법은 에라토스테네스의 체이다. 

 

<에라토스테네스의 체>

에라토스테네스를 자바로 구현한 코드이다. 

i = 2 ~ 100 

i는 2부터 시작해서 2를 제외한 2의 배수 자리에 모두 0을 대입하여 소수가 아님을 확인한다.

i가 3이 되면 앞의 방식과 동일하게 3을 제외한 3의 배수 자리에 모두 0을 대입한다. 

이 과정을 거치고 나서 arr배열의 0이 아닌 수만 출력하면 소수만 출력된다. 

public class Main {	
	static int N = 1;
    static int M = 100;
	static int[] arr = new int[M+1];
	
	public static void main(String[] args) {
		
		for(int i = 2; i <= M; i++) { // 2~M까지 자기 자신을 대입, 1은 소수가 아니기에 2부터 시작
			arr[i] = i;
		}
		
		for(int i = 2; i * i <= M; i++) {
			if(arr[i] == 0) 
            	continue; //이미 소수라고 판별 되었기에 continue.

			for(int j = i * i; j <= M; j+=i) {
				arr[j] = 0; //i의 배수는 소수가 아니기에 0을 대입하여 소수가 아니라는 표시를 함.
			}
		}
	}
}

 

---

 

<백준 문제>

1929번 - 소수 구하기 

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

1929번: 소수 구하기

이 문제는 에라토스테네스의 체 개념만 가지고 풀 수 있는 문제이다. 

특정 범위를 입력받아 소수가 아닌 수는 체로 걸러지고, 소수인 자연수들만 배열에 남게 된다. 

이 배열에서 0이 아닌 수만 출력하면 답이 된다. 

 

-> 1929번 코드

 

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

public class Main {
	static int[] arr = new int[1000001];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N, M;
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		for(int i = 2; i <= M; i++) { // 2~M까지 자기 자신을 대입 
			arr[i] = i;
		}
		
		for(int i = 2; i * i <= M; i++) {
			if(arr[i] == 0) continue; //소수라고 판별했기에 0을 대입 

			for(int j = i * i; j <= M; j+=i) {
				arr[j] = 0;
			}
		}
		
		for(int i = N; i <= M; i++) {
			if(arr[i] != 0) System.out.println(arr[i]);
		}
	}
}

---

1978 - 소수 찾기 

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

1978번: 소수 찾기

이 문제는 첫 줄에 N이 주어지고, 두 번째 줄에서 N개의 자연수를 입력받는다. 

두 번째 줄에서 입력받은 N개의 자연수 중에 소수는 몇 개인지 구하는 문제이다. 

1929번에서 특정 범위 안에서 소수를 찾는 것과는 조금 다른 문제이다. 

소수인지 아닌지 판별만 하면 되기에 입력받은 수의 제곱근을 이용하고, 2부터 해당 수의 제곱근까지의 범위에서 나머지가 0이 되는지 아닌지 확인하면 된다. 말은 어렵지만 코드로 보면 이해하기 편할 것이다.

-> 1978번 코드

 

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

public class Main {	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		br.readLine(); //N은 사용하지 않기에 따로 저장하지 않는다. 
		
		int cnt = 0; //소수의 개수 저장
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		while(st.hasMoreTokens()) { //while문 조건에서 N을 사용할 수도 있다. 
			int num = Integer.parseInt(st.nextToken());
			boolean isPrime = true;
			
			if(num == 1) continue; //1은 소수가 아니기에 continue
			
			for(int i = 2; i <= Math.sqrt(num); i++) {
				if(num % i == 0) { 
 					//나머지가 0이면 1과 자기자신이 아닌 약수가 존재한다는 의미이기에 소수가 아닌 것으로 판별
					isPrime = false;
					break; //한 번 소수가 아닌 것으로 판별되면 뒤는 확인할 필요 없기에 break
				}
			}
			
			if(isPrime) cnt++;
		}
		
		System.out.println(cnt);
	}
}

 

 

 

2023.02.01