问题陈述

生成尽可能多的不同质数P，使得反向（P）也是质数
并且不等于P。

输出：
每行打印一个整数（≤1015）。总共打印不超过
106个整数。

评分：
让N =正确的输出。 M =错误的输出。您的分数
将为最大值（0，N-M）。

注意：仅P和reverse（P）之一将被视为正确。如果两个文件都
，则将其视为不正确。

示例输出
107 13 31 17 2

说明
分数将为1。由于13,107,17是正确的。 31是不正确的，因为13已经存在。 2不正确。

时间限制2秒（时间限制是针对每个输入文件的。）

内存限制

源代码限制
25 KB原为：16.452秒

我的问题是，如果我们必须使用Python语言，是否可以进一步优化以下代码，是否可以将执行时间减少到2秒。 

from time import time
start = time()
lsta=[]   # empty list used to hold prime numbers created by primes function
LIMIT = pow(10,6)

# binary search function
def Bsearch(lsta,low,high,search):
    if low>high:
        return False
    else:
        mid=int((low+high)/2)
        if search<lsta[mid]:
            return(Bsearch(lsta,low,mid-1,search))
        elif search>lsta[mid]:
            return(Bsearch(lsta,mid+1,high,search))
        elif search==lsta[mid]:
            return True
        else:
            return False

# prime number creating function using sieve of Eras** algorithm
def primes(LIMIT):
    dicta = {}
    for i in range(2,LIMIT):
        dicta[i]=1
    for i in range(2,LIMIT):
        for j in range(i,LIMIT):
            if i*j>LIMIT:
                break
            dicta[i*j]=0
    for i in range(2,LIMIT):
        if(dicta[i]==1):
            lsta.append(i)

final = [] # used to hold the final output values
primes(LIMIT)
for i in range(len(lsta)):
    # prime number compared with reversed counterpart
    if(int(str(lsta[i])[::-1])<=lsta[len(lsta)-1]):
        if Bsearch(lsta,i+1,len(lsta)-1,int(str(lsta[i])[::-1])):
            if not(int(str(lsta[i])[::-1])==lsta[i]):
                final.append(str(lsta[i]))

for i in range(len(final)-1,0,-1):
    print(final[i])
print(13)
end=time()
print("Time Taken : ",end-start)


评论

有关生成素数的信息，请参见Eratosthenes筛-Python
为什么要等到编译完整个列表才能开始输出？
@DavidHarkness：条件是P是素数，其反向是素数，并且其反向不等于P。2满足前两个条件，但不满足第三个条件。
@StijndeWitt：不，没有（广泛理解的）质数定义要求将质数强制为奇数。这似乎是一个误会。
@Oddthinking：有趣，因为我记得认为2不是一个素数真的很愚蠢...似乎我的第一个直觉毕竟是对的...但是我对一个也有同样的感觉，但是我肯定是错的。顺便说一句，您的用户名现在非常适合:)

#1 楼

通过有效地实现Eratosthenes筛子和@tobias_k概述的一般方法，我可以在0.5秒内运行它，包括打印。尝试以下操作：

def primes(limit):
    # Keep only odd numbers in sieve, mapping from index to number is
    # num = 2 * idx + 3
    # The square of the number corresponding to idx then corresponds to:
    # idx2 = 2*idx*idx + 6*idx + 3
    sieve = [True] * (limit // 2)
    prime_numbers = set([2])
    for j in range(len(sieve)):
        if sieve[j]:
            new_prime = 2*j + 3
            prime_numbers.add(new_prime)
            for k in range((2*j+6)*j+3, len(sieve), new_prime):
                sieve[k] = False
    return prime_numbers


评论

\ $ \ begingroup \ $
您提出了一种替代解决方案，但尚未检查代码。请对其进行编辑，以说明您的推理（解决方案的工作原理以及对原始解决方案的改进），以便所有人都可以从您的思考过程中学习。
\ $ \ endgroup \ $
– Toby Speight
18年4月19日在10:42

#2 楼

您可以优化一些事情：


如果您（或分级服务器？）在Python 2.x上运行此程序，则绝对应该使用xrange而不是range（大约2
在素数筛中，仅当当前数是素数（低至1s）时，才需要检查倍数；另外，不要乘以i s的倍数。
使用规则数组而不是筛子中的字典（0.8s）
不要进行字符串转换和反转，而不必要的次数更多；另外，也可以使用set s快速查找（0.4s），而不是执行自己的二进制搜索。

我的版本（已更新）：

def primes(limit):
    numbers = [0, 0] + [1] * (limit-2)
    for i in xrange(2, limit):
        if numbers[i]:
            for k in xrange(i**2, limit, i):
                numbers[k] = 0
    return set(i for i, e in enumerate(numbers) if e)

ps = primes(LIMIT)
final = set()
for p in ps:
    q = int(str(p)[::-1])
    if p != q and q in ps and q not in final:
        final.add(p)


>不确定您的情况是否将运行时间从16s缩短为2s，但这可能是一个开始。作为一种绝望的措施，您可以减少LIMIT-最好不要发现太多，而要超时。

评论

\ $ \ begingroup \ $
谢谢您的建议，是的，我现在相信它的减少不能少于您在此处添加的内容，也许我应该用C或C ++编写此程序。
\ $ \ endgroup \ $
– Akash Rana
2014年3月31日17:17
\ $ \ begingroup \ $
在我看来，您的基本方法不错，但这并不是Erathostenes筛网的最佳实现。对于p！= q，检查p> 9是多余的，并且对于大多数数字来说放慢了速度。
\ $ \ endgroup \ $
– Jaime
2014年3月31日17:27
\ $ \ begingroup \ $
@Jaime感谢您的指导！我使用三参数范围（x）而不是乘以来改进筛子，但是为了提高可读性，并没有完全复制答案（+1），只剩下了奇数技巧。将时间再减少20％（您的时间甚至减少40％）。
\ $ \ endgroup \ $
–tobias_k
2014年3月31日在18:27
\ $ \ begingroup \ $
当i是素数时，要从筛子上移除的第一个非素数是i * i，而不是i * 2。我想你在哪里写i ** 2？这样可以节省更多时间，因为它避免了很多多余的筛分。
\ $ \ endgroup \ $
– Jaime
2014年3月31日在18:46
\ $ \ begingroup \ $
如果p！= ps中的q和q且q不是最终值：如果重写为p \ $ \ endgroup \ $
– Peter Taylor
18年4月19日在10:28

#3 楼

使用快速的素数生成器

请参见以下该线程（python 3）中最好的纯python素数生成器：

def primes(n):
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1, n//2) if sieve[i]]


使用一个python集

您可以使用本机python模块bisect执行二进制搜索。但是使用一组素数更简单，更快捷。有关时间复杂度的信息，请参见此页面：在原始素数上（以避免重复），然后在素数集中查找它：

prime_set = set(primes(upper_bound))


将运行逻辑与求解逻辑分开

它使参数化和测试程序（python 3）更加容易：

def palindromic_primes(upper_bound):
    prime_set = set(primes(upper_bound))
    for p in prime_set:
        r = int(str(p)[::-1])
        if r > p and r in prime_set:
            yield p


多个上限的结果

if __name__ == '__main__':
    t = time.time()
    upper_bound = int(eval(sys.argv[1]))
    generator = palindromic_primes(upper_bound)
    for score, x in enumerate(generator, 1):
        print(x)
    delta = time.time() - t
    status = "Score = {} in {:.3f} s".format(score, delta)
    print(status, file=sys.stderr)


评论

\ $ \ begingroup \ $
我想知道使用int→str→int转换来反转数字是否有限制。显而易见的算术方法会更快吗？
\ $ \ endgroup \ $
– Toby Speight
18年4月20日在13:03
\ $ \ begingroup \ $
@TobySpeight我刚刚对其进行了基准测试，字符串方法的速度大约快了3倍。
\ $ \ endgroup \ $
– Vincent
18年4月20日在14:31
\ $ \ begingroup \ $
这让我感到惊讶-感谢您的演示！
\ $ \ endgroup \ $
– Toby Speight
18年4月20日在14:34

#4 楼

使用numba甚至可以在不到一秒钟的时间内运行此代码。

('Time Taken : ', 0.7115190029144287)


稍​​微基于@jaime版本的代码应该用numpy.arrays重写。在这里看到

import numpy as np
import numba
from time import time
start = time()

LIMIT = pow(10,6)
# binary search function
def Bsearch(lsta,low,high,search):
    if low>high:
        return False
    else:
        mid=int((low+high)/2)
        if search<lsta[mid]:
            return(Bsearch(lsta,low,mid-1,search))
        elif search>lsta[mid]:
            return(Bsearch(lsta,mid+1,high,search))
        elif search==lsta[mid]:
            return True
        else:
            return False


def primes(limit):
    # Keep only odd numbers in sieve, mapping from index to number is
    # num = 2 * idx + 3
    # The square of the number corresponding to idx then corresponds to:
    # idx2 = 2*idx*idx + 6*idx + 3
    sieve = [True] * (limit // 2)
    prime_numbers = set([2])
    for j in range(len(sieve)):
        if sieve[j]:
            new_prime = 2*j + 3
            prime_numbers.add(new_prime)
            for k in range((2*j+6)*j+3, len(sieve), new_prime):
                sieve[k] = False
    return list(prime_numbers)



@numba.jit('void(uint8[:])', nopython=True)
def primes_util(sieve):
    ssz = sieve.shape[0]
    for j in xrange(ssz):
        if sieve[j]:
            new_prime = 2*j + 3
            for k in xrange((2*j+6)*j+3, ssz, new_prime):
                sieve[k] = False

def primes_numba(limit):
    sieve = np.ones(limit // 2, dtype=np.uint8)
    primes_util(sieve)

    return [2] + (np.nonzero(sieve)[0]*2 + 3).tolist()



final = [] # used to hold the final output values

lsta = primes_numba(LIMIT)

for i in xrange(len(lsta)):
    # prime number compared with reversed counterpart
    if(int(str(lsta[i])[::-1])<=lsta[len(lsta)-1]):
        if Bsearch(lsta,i+1,len(lsta)-1,int(str(lsta[i])[::-1])):
            if not(int(str(lsta[i])[::-1])==lsta[i]):
                final.append(str(lsta[i]))

for i in xrange(len(final)-1,0,-1):
    print(final[i])
print(13)

end=time()
print("Time Taken : ",end-start)


评论

\ $ \ begingroup \ $
您提出了一种替代解决方案，但尚未检查代码。请对其进行编辑，以说明您的推理（解决方案的工作原理以及对原始解决方案的改进），以便所有人都可以从您的思考过程中学习。
\ $ \ endgroup \ $
– Toby Speight
18年4月19日在10:43

#5 楼

这大约用了1350万个点，用了1350万个限制，在大约2秒钟内得到了

基本上，我的策略是创建一个由布尔组成的查找列表，在主循环的每个循环结束时，保证下一个比索引值高的下一个真值是质数。

评估新质数时，我要做的第一件事是从列表的其余部分中消除其倍数。

此后，我得到当前质数的倒数并执行：



Case1如果反转的值小于非反转的值，我使用查找列表检查它是否也是素数。如果它也是一个素数，则仅添加原始值。

情况2如果反转的值高于我的整体限制，我将使用通用素数评估功能对其进行简单检查。如果是素数，我添加非反向素数

Case3如果反向值高于非反向素数且小于限制，我将忽略它，因为在Case1 

from time import time
def is_prime(n):
    for i in xrange(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
def DoMath(limit):
    start = time()
    lkup = [True,True,True] +[ bool(ii%2) for ii in xrange(3,limit)]
    with open("text.txt", 'w') as file:
        index = 3
        r_index = 0
        str_index = ''
        while index <  limit:
            if lkup[index]:
                for ii in xrange(index*2, limit, index):
                    lkup[ii] = False
                str_index = str(index)
                r_index = int(str_index[::-1])
                if r_index >= limit and is_prime(r_index):
                    file.write(str_index+'\n')
                elif r_index < index and lkup[r_index]:
                    file.write(str_index+'\n')
            index += 1
    end=time()
    print("Time Taken : ",end-start)




评论

\ $ \ begingroup \ $
您提出了一种替代解决方案，但尚未检查代码。请对其进行编辑，以说明您的推理（解决方案的工作原理以及对原始解决方案的改进），以便所有人都可以从您的思考过程中学习。
\ $ \ endgroup \ $
– Toby Speight
18年4月19日在10:43