查找數字「內」的最大素數

Question

對於這個問題，我需要在更大的數字中找到最大的素數。爲了舉例說明，假設較大的數字是「123456789」，那麼我需要檢查的一些數字是12,456,234567等。

我寫了一些Python代碼來解決這個問題，但是我試圖檢查的數字運行速度非常慢。我正在使用的實際數字大約是10000位數，所以我需要查看很多數字。這裏是我的代碼：

num = "123456789" 

def isPrime(n): 
# 0 and 1 are not primes 
if n < 2: 
    return False 
# 2 is the only even prime number 
if n == 2: 
    return True 
# all other even numbers are not primes 
if not n & 1: 
    return False 
# range starts with 3 and only needs to go up the squareroot of n 
# for all odd numbers 
for x in range(3, long(n**0.5)+1, 2): 
    if n % x == 0: 
     return False 
return True 

def largestPrime(): 
    largest = 2 
    for i in range(0,len(num)): 
     for j in range(i+1,len(num)): 
      if isPrime(long(num[i:j])): 
       if long(num[i:j]) > largest: 
        largest =long(num[i:j]) 
    print largest 

def main(): 
    largestPrime() 

main() 

我敢肯定，這個代碼給出了正確的答案，但正如我所說，這是很慢。任何人都可以幫我弄清楚如何加快速度？

感謝您的幫助！

Answer 1

我可能會使用從數字總數開始並查看是否爲素數的策略。然後繼續將數字減一，同時向左移動以查看是否爲素數。讓我用一個例子解釋：

123456789 

First check the 9-digit number: 123456789 
Then check the 8-digit numbers: 23456789, 12345678 
Then Check the 7-digit numbers: 3456789, 2345678, 1234567 
etc. 

Answer 2

代碼：

def isprime(n): 
    if n == 2: 
     return str(n)+" is the biggest prime" 
    if n % 2 == 0: 
     return isprime(n-1) #not prime, check again for next biggest number 
    max = n**0.5+1 
    i = 3 
    while i <= max: 
     if n % i == 0: 
      return isprime(n-1) #not prime, check again for next biggest number 
     i+=2 
    return str(n)+" is the biggest prime" 

print "Testing 7:",isprime(7) 
print "Testing 23:",isprime(23) 
print "Testing 2245:",isprime(2245) 
print "Testing 222457:",isprime(222457) 
print "Testing 727245628:",isprime(727245628) 

輸出：

>>> 
Testing 7: 7 is the biggest prime 
Testing 23: 23 is the biggest prime 
Testing 2245: 2243 is the biggest prime 
Testing 222457: 222437 is the biggest prime 
Testing 727245628: 727245613 is the biggest prime 

Answer 3

一個問題，我看到的是，對於一些大的數字你要多次測試相同的數字。例如'123456712345671234567'，你的代碼將測試'1234567'三次。我建議你做一個不包含重複的集合，然後對每個數字進行主要測試。我也認爲排序數字是一個好主意，因爲我們可以在發現第一個素數後停下來。

接下來，如果您處理的是大數字（例如10000數字），我建議使用統計素數測試。下面我使用wikipedia的僞代碼進行了Miller-Rabin素數測試。

我已經幾乎重寫代碼：P

import random 
num = '3456647867843652345683947582397589235623896514759283590867843652345683947582397589235623896514759283590784235876867843652345683947582397589235623896514759283590784235876867843652345683947582397589235623896514759283590784235876867843652345683947582397589235623896514759283590784235876867843652345683947582397589235623896514759283590784235876867843652345683947582397589235623896514759283590784235876867843652345683947582397589235623896514759283590784235876784235876324650' 

def probablyPrime(num, k): 
    """Using Miller-Rabin primality test""" 
    if num == 2 or num == 3: 
     return True 
    if num < 2: 
     return False 
    if not num & 1: 
     return False 

    # find s and d such that n−1 = (2**s)*d with d odd 
    d = (num-1) >> 1 
    s = 1 
    while not (d & 1): 
     d = d >> 1 
     s += 1 

    # run k times 
    for _ in range(k): 
     a = random.randint(2, num-2) 
     x = pow(a, d, num) # more efficient than x = a**d % num 
     if not (x == 1 or x == num-1): 
      for _ in range(s-1): 
       x = (x**2) % num 
       if x == 1: 
        return False 
       if x == num-1: 
        break 
      if not x == num-1: 
       return False 
    return True 


def largestPrime(num): 
    num_list = set([]) 
    for i in range(0,len(num)+1): 
     for j in range(i+1,len(num)+1): 
      inum = int(num[i:j]) 
      # Don't append numbers that have already appeared 
      if inum not in num_list: 
       num_list.add(inum) 

    # Convert to list and sort 
    num_list = list(num_list) 
    num_list.sort(reverse=True) 

    for num in num_list: 
     print('Checking ' + str(num)) 
     if probablyPrime(num,100): 
      print('\n' + str(num) + ' is probably the largest prime!') 
      return 

largestPrime(num) 

，以提高速度也可能會蟒的multiprocessing包的另一種方法。