圆素数错误输出 Python 程序 [英] Circular prime numbers Incorrect Output Python Program

问题描述

问题陈述:

数字 197 被称为圆形素数，因为数字的所有旋转:197、971 和 719，它们本身都是素数.

100 以下的质数有 13 个:2、3、5、7、11、13、17、31、37、71、73、79 和 97.

一百万以下的圆素数有多少个?

我的问题我检查了所有代码，发现二进制搜索函数给出了一个 return 1 语句作为输出打印成功.但最终列表中没有添加任何内容.请帮忙

Python 编程:

 from time 导入时间开始 = 时间()LIMIT = 1000000 # 素数的最大极限prima = [] # 稍后由 primes 函数填充的素数列表# 二分查找功能def Bsearch(lsta,low,high,search):如果低>高:返回-1别的:mid = int((低+高)/2)如果搜索lsta[mid]:Bsearch(lsta,mid+1,high,search)elif 搜索==lsta[中]:打印(成功！")返回 1#素数生成函数# 使用 Era** 算法的筛选# 产生正确的测试结果定义素数(限制):lsta = {} # 临时空字典对于范围内的 i (2,LIMIT):lsta[i] = 1对于范围内的 i (2,LIMIT):对于范围内的 j(i,LIMIT):如果 i*j>LIMIT:休息lsta[i*j] = 0对于范围内的 i (2,LIMIT):如果(lsta[i]==1):prima.append(i)素数(极限)最终 = []对于初步项目:x = int(str(item)[::-1])# 真正的问题是下面的语句没有在最终列表中插入任何值if(Bsearch(prima,0,len(prima)-1,x)):打印(你好！")打印(最终)final.append(item)打印(最终)

解决方案

快速生成质数和列出圆形质数

def primes(max_n):数字 = 范围(3，max_n+1，2)一半 = (max_n)//2初始 = 4对于 xrange(3, max_n+1, 2) 中的步骤:对于 xrange 中的 i(初始、一半、步骤):数字[i-1] = 0初始 += 2*(步+1)如果初始 >一半:返回 [2] + 过滤器(无，数字)定义旋转(S_list):S=[]对于范围内的 i(len(S_list)):S.append(int(S_list[i:]+S_list[:i]))返回集(S​​)def circlePrime(限制):all_primes_in_limit = 素数(限制)圆形素数=[]reject_list=['0','2','4','5','6','8']All_primes_in_limit=[i for i in All_primes_in_limit if not any(j in reject_list for j in set(str(i)))]而 All_primes_in_limit:ShufleSet=rotate(str(All_primes_in_limit[-1]))PrimesSet=set(All_primes_in_limit)如果不是 ShufleSet - PrimesSet:circle_prime+=list(ShufleSet)All_primes_in_limit=list(PrimesSet-ShupleSet)circle_prime.sort()返回circle_prime#对于限制值 1000000打印circlePrime(1000000)

<块引用>

这是循环素数列表最快的算法

Problem Statement :

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

My Problem I have checked through all the code and found that the binary search function is giving a return 1 statement as the output print success. But nothing is added to the final list. Please Help

Program in Python :

from time import time
start = time()
LIMIT = 1000000   # largest limit of the prime numbers
prima = []   # list of primes later to be filled by primes function

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

# prime number generating function
# uses sieve of Era** algorithm
# produces correct result tested
def primes(LIMIT):
    lsta = {}  # temporaty empty dictionary
    for i in range(2,LIMIT):
        lsta[i] = 1
    for i in range(2,LIMIT):
        for j in range(i,LIMIT):
            if i*j>LIMIT:
                break
            lsta[i*j] = 0
    for i in range(2,LIMIT):
        if(lsta[i]==1):
            prima.append(i)
primes(LIMIT)

final = []
for item in prima:
    x = int(str(item)[::-1])
    # real problem here the following statement not inserting any value in final list
    if(Bsearch(prima,0,len(prima)-1,x)):
        print("Hello!")
        print(final)
        final.append(item)
print(final)

解决方案

Quickly generate prime numbers and list out Circular Prime numbers

def primes(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4
    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)

        if initial > half:
            return [2] + filter(None, numbers)


def rotate(S_list):
    S=[]
    for i in range(len(S_list)):
        S.append(int(S_list[i:]+S_list[:i]))
    return set(S)

def circularPrime(limit):
    All_primes_in_limit = primes(limit)
    circular_prime=[]
    reject_list=['0','2','4','5','6','8']
    All_primes_in_limit=[i for i in All_primes_in_limit if not any(j in reject_list for j in set(str(i)))]
    while All_primes_in_limit:
        ShufleSet=rotate(str(All_primes_in_limit[-1]))
        PrimesSet=set(All_primes_in_limit)
        if not ShufleSet -  PrimesSet:
            circular_prime+=list(ShufleSet)
        All_primes_in_limit=list(PrimesSet-ShufleSet)
    circular_prime.sort()
    return circular_prime


#for limit value 1000000
print circularPrime(1000000)

This is the fastest possible algorithm for circular prime number listing

这篇关于圆素数错误输出 Python 程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！