일단 전에 기출로 풀었는데 다시 복습할 겸 정리하기
만약 16인 소수인지 아닌지 구하는 방법은 단순하게
for(int i=2;i<16;i++){
if(16%i==0) {
System.out.println("소수가 아니다.")
break;
}
}
이렇게 하나하나 검사할 수도 있다.
하지만 아래 방법은 좀 더 간단하다.
16은
1 16
2 8
4 4
8 2
16 1
일 때
우리는 16의 루트값까지만 검사를 해도 그 절반은 안해도 된다.
즉 2~15까지 검사하는 것이 아니라 2~루트16까지만 검사하는 것이다.
위를 보면 pq=16이라고 보았을 때 하나는 증가하고 하나는 감소한다.
그 규칙이 일정하기 때문에 딱 그 절반만 검사해도 알 수 있다는 의미이다.
이를 에라토스테네스의 체에 응용해보고자 한다.
에라토스테네스의 체는 말 그대로 걸러준다는 것
예를 들어 16까지의 소수를 구할 때 이 에라토스테네스 체의 방법을 소수를 걸러내겠다는 것이다.
이 방법은
2를 제외한 2의 배수를 제거하고
3을 제외한 3의 배수를 제거한다.
4인 경우 2에 의해서 제거되었음으로 패스
5를 제외한 5의 배수를 제거한다.
이렇게 쭉 16까지 간다!
위에 배웠듯이 굳이 우리가 끝가지 갈 필요는 없다 어차피 발전은 제거되었다.
따라서 16까지 존재하는 소수를 구할 때도 그 절반까지만 진행한다.
백준 1929번 풀이방법을 첨부한다.
import java.util.*;
import java.io.*;
class Main{
public static boolean[] prime ; //boolean 기본값은 False
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
make_prime(M,N);
for(int i=M;i<prime.length;i++) {
if(prime[i]==false) bw.write(Integer.toString(i)+"\n");
}
bw.flush();
bw.close();
br.close();
}
public static void make_prime(int M , int N){
prime = new boolean[N+1];
if(N==1) return;
prime[0]=true; prime[1]=true;
for(int i=2;i<=Math.sqrt(N);i++){
if(prime[i]==true) continue;
for(int j=i*i;j<prime.length;j+=i){
prime[j]=true;
}
}
}