[수학] 백준 4134 다음 소수

4134번: 다음 소수

https://www.acmicpc.net/problem/4134

 

# 코드

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));
        StringBuilder sb = new StringBuilder();
        long t = Long.parseLong(br.readLine());

        // t만큼 반복
        for (long i = 0; i < t; i++) {
            long n = Long.parseLong(br.readLine());
            long x = n;

            while (true) {
                // 소수이면 sb에 담고 while문 탈출
                if (isPrime(x)) {
                    sb.append(x).append("\n");
                    break;
                }
                x++;
            }
        }
        System.out.print(sb);
        br.close();
    }

    // 소수 판별 함수
    public static boolean isPrime(long x) {
        // 0과 1은 소수가 아님
        if (x == 0 || x == 1) {
            return false;
        }

        // Math.sqrt() : 제곱근 함수
        for (int j = 2; j <= Math.sqrt(x); j++) {
            // 약수가 존재하면 소수가 아님
            if (x % j == 0) {
                return false;
            }
        }

        // 약수가 존재하지 않으면 소수
        return true;
    }
}

• 이전에 소수 찾기 문제에서 작성했던 isPrime() 코드를 그대로 가져와 사용한 초기 코드이다.

 

더 효율적인 코드가 있을 것 같아 다른 제출자분의 코드를 염탐했는데, 시간복잡도가 낮은 상위권 코드들은 모두 6의 배수를 활용하고 있었다.

그래서 아래는 타 코드를 참고해 새롭게 작성해본 코드이다.

설명은 주석으로 대신했다. :D

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));
        StringBuilder sb = new StringBuilder();
        long t = Long.parseLong(br.readLine());

        // t만큼 반복
        for (long i = 0; i < t; i++) {
            long x = Long.parseLong(br.readLine());
            while(!isPrime(x)) {
                x++;
            }
            sb.append(x).append('\n');
        }
        System.out.print(sb);
    }

    // 소수 판별 함수
    static boolean isPrime(long num) {
        // 0과 1은 소수가 아님
        if (num < 2) return false;

        // 2와 3은 소수임
        if (num == 2 || num == 3) return true;

        // 2 또는 3으로 나누어 떨어지면 소수가 아님
        if (num % 2 == 0 || num % 3 == 0) return false;

        // 5부터는 6씩 더하며 소수 판별
        // 5부터는 소수가 [6k ± 1] 형태이기 때문
        for (long i = 5; i <= Math.sqrt(num); i += 6) {
            // i 로 나눠 6k - 1 값을 판별하고
            // i+2 로 나눠 6k + 1 값을 판별함
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }

        // 소수일 경우 true 반환
        return true;
    }
}

 

 

+

새로운 코드로는 실행 시간이 거의 반으로 줄었다. (✿◡‿◡)

앞으로 소수 문제가 나오면 이렇게 푸는 것이 좋겠다.

위가 new code