Метод big.Int.ProbablyPrime

Метод ProbablyPrime выполняет вероятностную проверку на простоту для больших целых чисел, которые хранятся в типе big.Int. Метод принимает параметр n типа int, который определяет количество итераций теста Миллера-Рабина. Чем больше значение n, тем выше точность проверки: вероятность ложноположительного результата не превышает 1/4 в степени n. Метод возвращает true, если число вероятно является простым, и false, если число точно составное.

Синтаксис

func (x *big.Int) ProbablyPrime(n int) bool

Пример

Давайте проверим, является ли число 17 простым с использованием 10 итераций:

package main

import (
	"fmt"
	"math/big"
)

func main() {
	num := big.NewInt(17)
	res := num.ProbablyPrime(10)
	fmt.Println(res)
}

Результат выполнения кода:

true

Пример

Давайте проверим составное число 100, используя 20 итераций:

package main

import (
	"fmt"
	"math/big"
)

func main() {
	num := big.NewInt(100)
	res := num.ProbablyPrime(20)
	fmt.Println(res)
}

Результат выполнения кода:

false

Пример

Проверим очень большое число на простоту с различным количеством итераций:

package main

import (
	"fmt"
	"math/big"
)

func main() {
	num := new(big.Int)
	num.SetString("18446744073709551629", 10)
	
	res1 := num.ProbablyPrime(5)
	fmt.Printf("С 5 итерациями: %v\n", res1)
	
	res2 := num.ProbablyPrime(20)
	fmt.Printf("С 20 итерациями: %v\n", res2)
}

Результат выполнения кода:

"С 5 итерациями: true"
"С 20 итерациями: true"

Пример

Проверим отрицательное число, которое не может быть простым:

package main

import (
	"fmt"
	"math/big"
)

func main() {
	num := big.NewInt(-17)
	res := num.ProbablyPrime(10)
	fmt.Println(res)
}

Результат выполнения кода:

false

Смотрите также

метод big.Int.SetString,
который позволяет преобразовать строку в большое целое число
метод big.Int.Cmp,
который сравнивает два больших целых числа
функцию big.NewInt,
которая создает новое большое целое число из int64
метод big.Int.Exp,
который выполняет возведение в степень больших чисел