найти 200-значные простые числа, используя BigInteger - PullRequest
Новая
       51

найти 200-значные простые числа, используя BigInteger

2 голосов
/ 23 апреля 2019

Один из способов сделать это, который абсолютно работает, - от 0 до 200 простых чисел. Для этого я написал такой метод: 

var primeList = arrayListOf(BigInteger("2"))
fun findNextPrime(num : BigInteger): BigInteger {
    val n = num + BigInteger.ONE
    val sqrt = sqrt(num)
    for (bigInteger in primeList) {
        if(bigInteger > sqrt){
            return n
        }
        if(n % bigInteger == BigInteger.ZERO){
            return findNextPrime(num + BigInteger.ONE)
        }
    }
    return n;
}

Я добавляю числаЯ нахожу для PrimeList и проверяю только числа, меньшие, чем squareRoot. Даже если это был самый быстрый алгоритм, который я мог написать, но он занимает так много времени после нахождения миллиона цифр. Это только 7 цифр. Я, вероятно, умру, пока не достигнет 200цифр. (хотя мой ноутбук i7 8-го поколения). Итак, следующее, что я использовал, было следующее: 

n = 2 * 3 * 5 *... + 1

ну, n простое число, и этот метод довольно быстро использовать, чтобы перейти к старшим цифрам, нонет ничего точно, чтобы точно получить 200 цифр. Я получил 198 и 201 цифру. Но нет 200, код прост, но я все равно выкладываю: 

var all = BigInteger.ONE
primeList.forEach {
   all *= it
}
all++
println(all.toString().length)

Ответы [ 2 ]

3 голосов
/ 23 апреля 2019

в классе BigInteger есть метод, который называется: 

isProbablePrime(int)

, он использует тот же алгоритм, который использовал наш друг здесь : но он также проверяет результат с помощью другого алгоритма.аккуратный.

3 голосов
/ 23 апреля 2019

Неверно, что 1 + произведение первых n простых чисел всегда простое. Возможно, вы неправильно оценили его роль в доказательстве бесконечного числа простых чисел. верно , что если p_1, p_2, ..., p_n являются первыми n простыми числами, то 

p_1 * p_2 * ... * p_n + 1

либо простое число, либо содержит главный фактор, который больше, чем любой из этих p_i, но это согласуется с составным числом. Обратитесь к статье Википедии о первоцветах для получения дополнительной информации.

В случае попытки получения 200 цифр произведение первых 92 простых чисел + 1 имеет 199 цифр, а произведение первых 93 простых чисел + 1 имеет 201 цифру. В обоих случаях тест Миллера-Рабина показывает, что они составные. Я не смог вычислить однозначное число из 199, но однозначное число из 201 равно 

509558935064289364432032169616857776489168568369134671296055828054188240764364761921821351373922822013621199759688858354748131233614846920025560717744496960296617420071391914813530238313960697008021211 = 11587 * 43976778723076669062918112506848863078378231498156094873224806080451216083918595142989673890905568483094951217717170825472351016968572272376418461874902646094469441621765074205016849772500275913353

С числами этой величины единственный эффективный способ получить простое число - случайным образом сгенерировать число кандидата целевого размера и проверить его на простоту (используя что-то вроде теста Миллера-Рабина). По теореме о простых числах 200-значные простые числа относительно многочисленны, поэтому на практике вы можете найти такое простое число очень быстро. Например, скрипт Python, который я написал с помощью Миллера-Рабина, выполнил следующую простую 200-значную цифру менее чем за секунду: 

49675218696612399034240799519655205503986657506787162015105425670413948962864456158664793804627084299081036134562339483478437262146378569515417671690110863951848724044479367633926630234074394356492223

При редактировании : Вот скрипт Python, который я использовал для поиска 200-значного простого числа. Код был для класса, который я преподавал в области криптографии, поэтому я написал его, чтобы его было проще обсуждать, а не было кратким или эффективным: 

import random

#The following function finds s and d in
#n-1 = 2^s*d with d odd
def findSD(n):
    s = 0
    d = n-1
    while d % 2 == 0:
        s = s + 1
        d = d//2
    return s,d

def checkBase(a,n):
    s,d = findSD(n)
    x = pow(a,d,n)
    if x == 1 or x == n-1:
        return "probable prime"
    else:
        for i in range(s-1):
            x = pow(x,2,n)
            if x == 1:
                return "composite"
            elif x == n-1:
                return "probable prime"
        #if you get to this stage, -1 not reached despite s-1
        #squarings -- so must be composite
        return "composite"

def MSR(n,k):
    #Implements the Miller-Selfridge-Rabin test for primality
    for i in range(k):
        a = random.randint(2,n-2)
        if checkBase(a,n) == "composite":
            return "composite"
    #if you get here n has survived k potential witnesses, so
    return "probable prime"

#The following function is slightly different from the one discussed in class:

def prime(n):
    smallPrimes = [2,3,5,7,11,13,17,19]

    for p in smallPrimes:
        if n == p:
            return True
        elif n % p == 0:
            return False

    if MSR(n,20) == "composite":
        return False
    else:
        return True

def findPrime(maxN):
    while True:
        m = random.randint(1,maxN//2)
        n = 2*m+1
        if prime(n):
            return n

Например, findPrime(10**200) обычно дает 200-значное простое число (хотя возможно получить 199-значное или даже меньшее число).

...