백준 5615번 문제를 풀 때 대부분은 Miller-Rabin을 직접 구현한 후에 사용한다. 풀이 방법에 대한 게시글들도 적어도 내가 본 것들은 전부 그러하였기 때문에, Golang에서 사용이 확인된 또 다른 소수 판별법을 이용하여 문제를 풀어보고, 풀이가 매우 간단하므로 이 함수에 사용된 개념에 대해 서술하려고 한다.
Backgrounds
밀러-라빈 알고리즘과 베일리-PSW 알고리즘 모두 확률적 알고리즘이다.
- Miller-Rabin(밀러-라빈)
- 서술 예정
- Baillie-PSW(베일리-PSW)
- 서술 예정
ProbablyPrime
math/big 패키지의 함수로, x.ProbablyPrime(n)의 형태로 사용되었다. x가 소수인지 아닌지를 판단하여 bool 값으로 return 해준다.
input이 2의 64제곱보다 작은 수 인 경우에, ProbablyPrime 함수의 정확도는 100%이다.[1][2]
Go 1.8 이상의 버전에서, n=0일 때는 베일리-PSW 방법만을 사용하여 소수인지 아닌지를 판별한다. 1.8 미만의 버전에서 n=0일 때는 panic 상태에 빠진다.
자세한 것은 하단 Reference의 Golang ProbablyPrime Function를 참고하라.
Solving Process & Answer Code
package main
import (
"bufio"
"fmt"
"math/big"
"os"
)
var reader = bufio.NewReader(os.Stdin)
func main() {
var n, cnt int64 = 0, 0
fmt.Fscan(reader, &n)
tmp2 := big.NewInt(1)
var i int64 = 0
for i = 1; i <= n; i++ {
var s string
fmt.Fscan(reader, &s)
tmp, _ := new(big.Int).SetString(s, 10)
//tmp = 2s+1
tmp.Add(tmp, tmp)
tmp.Add(tmp, tmp2)
// about ProbablyPrime function... https://golang.org/pkg/math/big/#Int.ProbablyPrime
// ProbablyPrime is 100% accurate for inputs less than 2^64, for larger inputs it is accurate (1 - 1/4^n) when set function as x.ProbablyPrime(n).
// If n==0, Up to Go 1.8, ProbablyPrime(0) is apply only a Baillie-PSW primality test.
if tmp.ProbablyPrime(0) {
cnt++
}
}
fmt.Println(cnt)
}
Reference
Definition of Probable Prime
Golang ProbablyPrime Function
5615번: 아파트 임대
[1] Menezes et al., Handbook of Applied Cryptography, 1997, pp. 145-149
[2] FIPS 186-4 Appendix F