[백준 / Go] 4134번: 다음 소수

문제

4134번: 다음 소수

정수 n(0 ≤ n ≤ 4*10⁹)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

---

문제 이해하기

 소수는 1과 자기 자신만을 약수로가지는 수입니다. 따라서 정수 n이 주어졌을 때 2 ≤ i ≤ (n-1)인 정수 i 중 어떤 것으로든 n을 0으로 나누어 떨어지게 만들 수 있다면 n은 소수가 아닌 것이죠. 

 

 그런데 정수 n의 범위(0 ≤ n ≤ 4*10⁹)를 보니 최댓값이 상당히 큽니다. 매 테스트 케이스마다 이런 값이 주어진다면 시간 초과가 발생하기 십상입니다. 어떻게 하면 시간을 줄일 수 있을까요?

 

 24를 예로 들어보겠습니다. 24의 약수는 1, 2, 4, 6, 12, 24입니다. 또 24를 1*24, 2*12, 4*6으로 나타낼 수도 있죠. 24가 2로 나누어 떨어짐은 곧 12로 나누어 떨어짐을 의미하며, 4로 나누어 떨어짐은 곧 6으로 나누어 떨어짐을 의미합니다. 즉, 나열된 약수들 중 어떤 수를 기준으로 왼쪽에 있는 수들로 24를 나누어 떨어지게할 수 있다면 오른쪽에 있는 수들은 더 볼 일이 없다는 것입니다. 여기서 왼쪽과 오른쪽을 나누는 어떤 수는 정수 n의 제곱근입니다. 24의 제곱근은 2√6입니다. 4보다 크고 6보다 작은 값이죠. 따라서 정수 n이 소수인지 판별하기 위해서는 2 ≤ i ≤ √n 범위의 정수들만 살펴보면 되는 것입니다. 여기서 √n을 포함해야 하는 이유는 제곱수 때문입니다. 예를 들어, 121의 약수는 1, 11, 121입니다. 11은 121의 제곱근이며 121을 0으로 나누어 떨어지게 만들 수 있기 때문에 검사하는 범위에 포함되어야 합니다.

---

코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	scanner = bufio.NewScanner(os.Stdin)
	writer  = bufio.NewWriter(os.Stdout)
	T       int
)

func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanWords)

	Setup()
	Solve()
}

func Setup() {
	T = scanInt()
}

func Solve() {
	for i := 1; i <= T; i++ {
		n := scanInt()

		for {
			if isPrime(n) {
				fmt.Fprintln(writer, n)
				break
			}

			n++
		}
	}
}

func isPrime(n int) bool {
	if n < 2 {
		return false
	}

	for i := 2; i*i <= n; i++ { // i*i <= n이나 i <= int(math.Sqrt(n))이나 마찬가지
		if n%i == 0 {
			return false
		}
	}

	return true
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func mustParseInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func scanInt() int {
	return mustParseInt(scanString())
}

시간: 264 ms

메모리:820 KB

분류: 수학, 브루트포스, 정수론, 소수 판정

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!