Go: Check if a number is prime

Ints

For integer types, use ProbablyPrime(0) from package math/big. (This primality test is 100% accurate for inputs less than 264.)

const i = 1212121
if big.NewInt(i).ProbablyPrime(0) {
	fmt.Println(i, "is prime")
} else {
	fmt.Println(i, "is not prime")
}
1212121 is prime

Larger numbers

For larger numbers, you need to provide the desired number of tests n to ProbablyPrime(n). For n tests, the probability of returning true for a randomly chosen non-prime is at most (1/4)n. A common choice is to use n = 20; it gives the false positive rate 0.000,000,000,001.

z := new(big.Int)
fmt.Sscan("170141183460469231731687303715884105727", z)
if z.ProbablyPrime(20) {
	fmt.Println(z, "is probably prime")
} else {
	fmt.Println(z, "is not prime")
}
170141183460469231731687303715884105727 is probably prime

Comments

Be the first to comment!