Python простые фибоначчи

Question

Простое описание проблемы Фибоначчи Даны два числа n1 и n2

1. Найдите простые числа между n1 и n2, затем

2. Сделайте все возможное уникальным комбинации чисел из списка простых чисел, которые вы нашли на шаге 1.

3. В этом новом списке снова найдите все простые числа.

4. Найти наименьшее (a) и наибольшее (b) число из 2-го сгенерированного списка, также считается в этом списке.

5. Считайте наименьшее и наибольшее число как 1-е и 2-е числа для генерации рядов Фибоначчи соответственно до подсчета (количество простых чисел во втором списке).

6. Вывести последнее число ряда Фибоначчи в качестве вывода

Ограничения 2 <= n1, n2 <= 100 </p>

n2 - n1> = 35

Формат ввода Одна строка, содержащая два целых числа, разделенных пробелами, n1 и n2.

Выходные данные Последнее число сгенерированный ряд Фибоначчи.

Тайм-аут 1

Тестовый пример 1

Вход

2 40

Выход

13158006689

Пояснение

1-й список простых чисел = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Комбинация всех простых чисел = [23, 25, 27, 211, 213, 217, 219, 223, 229 , 231, 32, 35, 37, 311, 313, 319, 323, 329, 331, 337, 52, 53, 57, 511, 513, 517, 519, 523, 529, 531, 537, 72, 73, 75 , 711, 713, 717, 719, 723, 729, 731, 737, 112, 113, 115, 117, 1113, 1117, 1119, 1123, 1129, 1131, 1137, 132, 133, 135, 137, 1311, 1317 , 1319, 1323, 1329, 1331, 1337, 172, 173, 175, 177, 1711, 1713, 1719, 1723, 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913, 1917, 1923, 1929 , 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 2319, 2329, 2331, 2337, 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931, 2937, 312 , 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 372, 373, 375, 377, 3711, 3713, 3717, 3719, 3723, 3729, 3731]

2-й прайм-лист = [193, 3137, 197, 2311, 3719, 73, 137, 331, 523, 1931, 719, 337, 211, 23, 1117, 223, 1123, 229, 37, 293, 2917, 1319, 1129, 233, 173, 3119, 113, 53, 373, 311, 313, 1913, 1723, 317]

наименьшее (a) = 23

наибольшее (b) = 3719

Следовательно, последнее число ряда Фибоначчи, т.е. 34-е число Фибоначчи в ряду, в котором 23 и 3719 являются первыми двумя числами. равно 13158006689

Пример 2

Вход

30 70

Выход

2027041

Пояснение

1-й простой список = [31, 37, 41, 43, 47, 53, 59, 61, 67]

2-й простой список, сгенерированный из комбинации 1-го простого списка = [3137, 5953, 5347, 6761 , 3761, 4337, 6737, 6131, 3767, 4759, 4153, 3167, 4159, 6143]

наименьшее простое число во втором списке = 3137 наибольшее простое число во втором списке = 6761

Следовательно, Последнее число в серии Фибоначчи, т.е. 14-е число Фибоначчи в серии, в которой 3137 и 6761 являются первыми двумя числами, это 2027041

from itertools import permutations
def isPrime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    else:
        return True
def listPrime(n1,n2):
    lis=[]
    for ele in range(n1,n2+1):
        if isPrime(ele)==True:
            lis.append(ele)
    return lis

def returnPrime(lis):
    r=[]
    for ele in lis:
        if isPrime(ele)==True:
            r.append(ele)
    return r

def fibo(mi,ma,c):
    f=mi
    s=ma
    res=[]
    res.append(f)
    res.append(s)
    for i in range(2,c):
        next=f+s  
        res.append(next)
        f,s=s,next
    return res[-1]

def main(n1,n2):
    primeNo=listPrime(n1,n2)
    comb=permutations(primeNo,2)
    r=[]
    for ele in comb:
        r.append(int(str(ele[0])+str(ele[1])))
    comb2=returnPrime(r)
    count=len(comb2)
    mini=min(comb2)
    maxi=max(com2)
    res=fibo(mini,maxi,count)
    return res


if __name__=="__main__":
    lis=list(map(int,input().split()))
    lis[0]=n1
    lis[1]=n2
    res=main(n1,n2)
    print(res)

Пожалуйста, помогите мне написать правильное решение для кода Также помогите мне выбрать изобразите его, чтобы он работал менее 1 секунды

Answer 1

def check_prime(x):
   if x&1 == 0: return 0
   for i in range(3,int(x**0.5)+1,2):
     if x%i==0: return 0
   return 1

n1,n2 = 30,70
min = 9789
max = 23
count = 0
freq = {}
if n1&1 == 0:
   l = [i for i in range(n1+1,n2+1,2) if check_prime(i)]
else:
   l = [i for i in range(n1,n2+1,2) if check_prime(i)]
if n1 == 2: l = [2] + l
for x in l:
   for y in l:
      if x != y:
         n = int(str(x)+str(y))
         if n not in freq:
            if check_prime(n):
                freq[n] = 1
                if n<min: min = n
                elif n>max: max = n
                count += 1
while count>1:
   min,max = max,min+max
   count -= 1

print(min)

Answer 2

Профиль, в котором проводится больше всего времени. Безумное предположение будет isPrime(..). Так что попробуйте это оптимизировать.

1. Ускорение на 2, проверяя четность отдельно, а затем проверяя только l oop только нечетные числа.

1б. Вы можете улучшить это еще больше, сохраняя список первых m простых чисел и проверяя их заранее.

вы можете хранить найденные простые числа до определенного значения, и каждое число, меньшее, чем наивысшее из ваших простых чисел, которое не входит в набор ваших простых чисел, не является простым.

Есть много хитрые способы реализации isPrime(...) просто погуглите, и вы найдете огромное количество идей по оптимизации.