Prime Numbers

4948 source: https://www.acmicpc.net/problem/4948
1929 source: https://www.acmicpc.net/problem/1929
ref: https://codereview.stackexchange.com/questions/24704/efficiently-determining-if-a-number-is-prime

백준에서 자바 입출력 하는방법 익숙해지자...
(BufferReader 활용)

https://rhsalska55.tistory.com/6 ; 다양한 입출력 상황 예시
https://st-lab.tistory.com/75 ; BufferReader vs Scanner 예제

백준 4948.

자연수 n이 주어졌을 때 n 초과 2n 이하에서 소수의 개수를 구하라.

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
• 입력의 마지막에는 0이 주어진다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int n = Integer.parseInt(br.readLine());
            // 입력이 여러 줄인 경우 while과 if+break로 여러줄 반복 및 종료
            if (n == 0) break;

            // 1 <= n <= 123456
            // 자연수 n이 주어졌을 때 n 초과 2n 이하 소수개수 구하라
            // 주어진 범위에 의해 i는 항상 2 이상임.
            int prime = 0;
            for(int i = n+1; i<=2*n; i++){
                prime = prime + isPrime(i);
            }
            System.out.println(prime);
        }
    }
    public static int isPrime(int n){
        if(n==2||n==3)
            return 1;
        else if(n%2==0)
            return 0;
        else{
            for(int j=3;j<=Math.sqrt(n);j+=2){ // 홀수만 고려
                if(n%j==0)
                    return 0;
            }
            return 1;
        }
    }
}

시간복잡도 줄이기
1. 2 제외한 짝수는 모두 소수가 아니다.
2. Math.sqrt(n)까지만 반복한다.
예를 들어 45의 경우 (3,15), (5,9) 과 같은 순서쌍이 생길 텐데,
3과 5에서 나누어지는지 확인했다면 9와 15에서는 확인하지 않아도 된다.

백준 1929.

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

• 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.
• (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
• 한 줄에 하나씩, 증가하는 순서대로 소수를 출력할것.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        for(int i = M; i<=N; i++){
            if (isPrime(i)==1)
                System.out.println(i);
            }
        }
    public static int isPrime(int n){
        if(n==1)
            return 0;
        else if(n==2 || n==3)
            return 1;
        else if(n%2==0)
            return 0;
        else{
            for(int j=3;j<=Math.sqrt(n);j+=2){
                if(n%j==0)
                    return 0;
            }
            return 1;
        }
    }


}

한편 위에서 사용된 것보다 효율적인 알고리즘들이 많은데, 그 중 대표적인 것이

에라토스테네스의 체(Sieve of Eratosthenes)

ref: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes