정수론

수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻합니다. 

모든 정수론을 공부하는 것은 비효율적이니 코딩테스트에 자주 등장하는 소수와 호제법 부분을 다루겠습니다. 

[소수 구하기]

- 자기 자신보다 작은 두 수의 곱으로 표현할 수 없는 1보다 작은 자연수 

- 1과 자기 자신 이외의 약수가 존재하지 않는 수

[에라토스테네스의 체]

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다. 
2. 2부터 시작하고 현재 숫자가 지워지지 않을때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다. 
3. 범위의 끝값의 제곱근까지 과정을 반복하고 2번 과정을 반복하고 남아 있는 모든 수를 출력합니다. 

ex) 1부터 30까지의 수 중 소수를 구하기 

• 1은 소수가 아니므로 삭제합니다. 
• 2부터 시작하고, 2의 배수를 모두 삭제합니다. 처음으로 선택된 2는 삭제하지 않습니다. 
• 다음으로 지워지지 않은 수 3을 선택하고, 3의 배수를 삭제합니다. 처음으로 선택된 3은 삭제하지 않습니다. 
• 과정을 반복하다가 남은 수를 출력합니다. 
• 2 3 5 7 11 13 17 19 23 29

시간 복잡도 O(Nlog(logN))

2중 for문으로 구현하지만, 배수를 삭제하는 연산을 함으로써 실제 구현에서는 바깥쪽 for문을 생략하는 경우가 빈번합니다.

백준 1929 실버 2

문제보기

• 3~16의 원소를 담을 배열을 생성하고, 에라토스테네스의 체 원리를 적용합니다.

package numberTheory;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _1929_소수구하기 {
    
    //일반적인 소수 구하기 방법
    /*
        2이상의 자연수를 자기 자신보다 작은 수로 나눴을 때, 나머지가 0이 아닌 수를 찾습니다. 
        문제의 두 수의 최대 범위가 1,000,000이므로 시간 초과가 날 수 있다. 
        일단 비교를 위해 시간초과가 나도록 문제를 풀어보겠다. 
    */
    
    //시간초과가 나는 일반적인 방법
    /*
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        OUT:
        for(int i=M; i<N;i++) {
            for(int k=2; k<i;k++) {
                if(i%k == 0) {
                    continue OUT; //추가하지 않고 다음으로 넘어감
                }
            }    
            sb.append(i).append(' ');
        }
        
        System.out.println(sb);
        
    }
    */
    
    //시간 복잡도를 줄인 방법 2
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        int arr[] = new int[N+1];
        
        //0번지는 버리고 1은 어차피 소수가 아니니까 버림
        for(int i=2;i<=N;i++) {
            arr[i] = i;
        }
        
        //N의 제곱근 까지만 탐색하면 된다. 
        //N = a*a라고 가정할 때, a는 N의 제곱근보다 클 수 없다. 
        //예를 들어 16의 범위까지 소수를 구할 때, 16 = 4 * 4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게된다.
        //4보다 큰 약수는 4보다 작은 수의 배수로 지울 수 있습니다.
        for(int i=2;i<=Math.sqrt(N);i++) {
            if(arr[i]==0) continue;
            
            for(int k = i+i; k<=N; k+=i ) {//k의 배수값 지우기 이런식으로 내부 반복에서 값을 지우고 외부 반복에서 지워진 값을 건너 뛰면서 시간복잡도 줄이기 가능
                arr[k] = 0;
            }
        }
        
        for(int i=M;i<=N;i++){
            if(arr[i] != 0) {
                System.out.print(i + " ");
            }
        }
        
    }
    
    
 
}