1929. <소수 구하기>

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

m 이상 n이하의 소수를 출력해야함

range는 100만 이하.

시간 제한은 2초이다.

 

1. 소수를 판별하는 알고리즘

뭐 냅다 i=2부터 몇까지 나머지 있으면 false이런식으로 하는것도 있지만 시간적으로 효율적이지 않아서 웬만하면

에라스토텔레스의 체라는 알고리즘을 활용한다.

 

i=2부터 n까지가 아닌 n의 제곱근까지만 search 해도 괜찮다.

  public static boolean isPrime(int num) {
        if(num <= 1) {
            return false;
        }
        for(int i=2; i*i<=num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

그 이유는 >>   제곱근까지만 검사하는 이유는, 만약 어떤 수가 소수가 아니라면 그 수의 약수 중 적어도 하나는 그 수의 제곱근 이하라는 수학적 사실 때문입니다. 따라서 제곱근 이하의 수만 검사해도 충분합니다.

어렵게 생각든다면 해보면 된다. 예를들어 10을 판별한다. 루트 10은 대충 뭐 3.xx일텐데, 10의 약수중 하나 인 2가 있다.

2는 10을 나머지 없이 나눌수있기에 10은 소수가 아니다. 즉 소수가 아닌 수는 약수가 존재한다는 아이디어인 것이다.

 

이 코드에서 아이디어를 좀 더 발전 시켜보면

여기다가 배열을 추가하는 것이다.

 

숫자들을 순서로 쭉 나열해 소수 인것과 아닌것을 하나의 배열로 담아서 관찰한다는 아이디어.

아래 이중 for문이 이해가 잘 안갈수 있는데

겉의 for문은 아까 위에서 설명한것과 동일하고

안의 for문 j=i*i 부터 j,=x 까지 j+=i를 한다?

간단하다. 위에서 모든값을 true로 만들었기에, 우리는 소수가 아닌 녀석들만 필터링하면된다.

따라서 안의 j=i^2부터 j+=i한 이유는 2의배수 (4부터 시작을 쭉 지우고), 

다음 3의배수를 쭉 지우고 이런식으로 소수를 필터링하는 것이다.

 

 

 저 아래 코드에서 좀 더 발전시키자면, stringbuilder을 활용하면 조금 더 시간적으로 여유가 생기겠다.

import java.util.*;

public class Main {
	public static boolean[] primearr(int x){
		boolean[] isprime = new boolean[x+1];
		Arrays.fill(isprime, true);
		isprime[0] = isprime[1] = false;
		for(int i=2; i*i<=x; i++) {
			if(isprime[i]) {
				for (int j = i * i; j <= x; j += i) {
                    isprime[j] = false;
                }
			}
		}
		return isprime;
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int first = Integer.parseInt(st.nextToken());
		int second = Integer.parseInt(st.nextToken());
		
		boolean[] primearr = primearr(second);
		for(int i=0; i<=second; i++) {
			if(primearr[i] == true) {
				if(i >=first && i<=second) {
					System.out.println(i);
				}
			}
		}

	}

}