[백준 1978, 1929, 6588] 소수에 대하여

소수(Prime Number)란?

약수가 1과 자기 자신 밖에 없는 수.

 

정수 n이 소수가 되려면

1. 2보다 크거나 같고,

2. n-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

boolean isPrimeNum(int a){
    if (a < 2) {
        return false;
    }
    for (int i = 2; i  <= n-1 ; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 

2번 조건을 더 발전시켜 생각해본다.

1. n = a * b

2. a가 작을 수록 b는 크다.

3. a 중 가장 작은 값은 2이다.

4. b는 n/2를 넘지 않는다.

 

즉, 정수 n이 소수가 되려면

1. 2보다 크거나 같고,

2. n/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

 

boolean isPrimeNum(int a){
    if (a < 2) {
        return false;
    }
    for (int i = 2; i  <= n/2 ; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 

여기서 더 2번조건을 발전시켜본다.

1. n = a * b (a <= b)

2. a <=  $ \sqrt{n} $  && b >= \sqrt{n}

3. a 와 b의 차이가 가장 작은 경우는 루트 n이다.

4. 따라서 루트 n까지만 검사하면 된다.

 

즉, 정수 n이 소수가 되려면

1. 2보다 크거나 같고,

2. 루트n 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

 

boolean isPrimeNum(int a){
    if (a < 2) {
        return false;
    }
    for (int i = 2; i*i <= n ; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 

[백준 1978] 소수찾기 문제

public class Baekjoon1978 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int result = 0;

        for (int i = 0; i < n; i++) {
            int t = Integer.parseInt(st.nextToken());
            if (isPrimeNum(t)) {
                result++;
            }
        }
        System.out.println(result);
    }
    static boolean isPrimeNum(int a){
        if (a < 2) {
            return false;
        }
        for (int i = 2; i * i <= a; i++) {
            if (a % i == 0) {
                return false;
            }
        }
        return true;
    }

}

 

에라토스테네스의 체

위의 방법으로 어떤 수 n이 소수인지 아닌지 판별하는 데 걸리는 시간복잡도는 O(루트n)이다.

1~10000000까지 모두 소수를 구하는 데 걸리는 시간은 10초로 너무 긴 시간이 필요하다.

 

따라서 1~n범위 안에 들어가는 모든 소수를 구하기 위해 에라토스테네스의 체를 사용한다.

1. 2~n까지 모든 수를 써놓는다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3. 그 수는 소수이다.

4. 이제 그 수의 배수를 다 지운다.

 

int prime[100] = new int[];
int pn = 0;
boolean check[101] = new boolean[];
int n = 0;

for(int i = 2; i <= n ; i++){
	if(check[i] == false){
    	prime[pn++] = i;
        for(int j = i*i; i j <= n ; j+=i){
        	check[j] = true;
        }
    }
}

 

안쪽 for문의 j 를 i*i 로 쓰는 경우 int의 최대값을 넘을 수 있기 때문에

i + i 혹은 i * 2로 바꿔주는 것이 좋다.\

 

[백준1929] 소수 구하기

package mathematics;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baekjoon1929 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        boolean check[] = new boolean[n + 1];

        check[0] = check[1] = true;

        for (int i = 2; i <= n; i++) {
            if(check[i]) continue;

            for(int j=i*2; j<=n; j+=i){
                check[j] = true;
            }
        }

        for(int i = m; i <= n; i++) {
            if(!check[i]) sb.append(i).append('\n');
        }

        System.out.println(sb);
    }

}