Staniczek1996viz
Rozwiązane

Python 15. Napisz program, który wypisze jakie liczby z ciagu Fibonacciego do 10000 sa jednoczesnie liczbami pierwszymi.
Do sprawdzenia czy liczba jest pierwsza mozna uzyc funkcji z zadania 3.

def czy_pierwsza(n):
if n == 2:
return True
if n % 2 == 0 or n <= 1:
return False

pierw = int(n**0.5) + 1
for dzielnik in range(3, pierw, 2):
if n % dzielnik == 0:
return False
return True

Odpowiedź :

Mrfixviz

Rozumiem, że z tymi 10000 to chodzi o wartość liczby w ciągu Fibonacciego, a nie ilość liczb w ciągu bo tyle to by się pewnie z tydzień liczyło.

Wykorzystałem własną funkcję do sprawdzania liczby pierwszej, ale w poniższym kodzie źródłowym jest też wskazana przez Ciebie funkcja - jeśli chcesz jej użyć wystarczy zakomentować/wywalić funkcję 'liczbaPierwsza()', odkomentować 'czy_pierwsza()' i zmienić nazwę sprawdzanej funkcji w warunku if. Wyniki są takie same.

W wyniku wyświetlam ciąg Fibonacciego z wartościami do 10000, a później liczby pierwsze. Można to usunąć wyrzucając deklarację zmiennej 'listaFibonacci', pierwszą linijkę pod pętlą while i pierwszego printa.

<kod>

def ciagFibonacciego(n):

   if n == 0:

       return 0

   elif n == 1:

       return 1

   else:

       return ciagFibonacciego(n - 1) + ciagFibonacciego(n - 2)

def liczbaPierwsza(n):

   if n <= 1:

       return False

   for i in range(2, n):

       if n % i == 0:

           return False

   return True

# def czy_pierwsza(n):

#     if n == 2:

#         return True

#     if n % 2 == 0 or n <= 1:

#         return False

#     pierw = int(n**0.5) + 1

#     for dzielnik in range(3, pierw, 2):

#         if n % dzielnik == 0:

#             return False

#     return True

listaFibonacci = []

listaPierwszych = []

i = 1

while ciagFibonacciego(i) <= 10000:

   listaFibonacci.append(ciagFibonacciego(i))

   if liczbaPierwsza(ciagFibonacciego(i)):

       listaPierwszych.append(ciagFibonacciego(i))

   i += 1

print(f"Lista elementów ciągu Fibonacciego do 10000: {listaFibonacci}")

print(f"Lista liczb pierwszych z powyższego: {listaPierwszych}")

</kod>

Adikac919viz

Do rozwiązania użyłem sita erastotenesa, w którym dodałem wszystkie liczby pierwsze do 10000 zbioru, a w samej funkcji używam podejścia dynamicznego do obliczania kolejnych liczb z ciągu fibonacciego, a następnie sprawdzam czy są one w zbiorze liczb pierwszych, jeśli tak to dodajemy je do listy która będzie outputem. Zamiast sita możemy użyć dowolnego algorytmu(na przykład tej podanej) do sprawdzania pierwszości liczb, sito jednak ma najlepszą złożoność.

def sieve_of_erastothenes(b):

   seq_primes=list(range(2, b + 1))

   sieve_set=set(range(2, b + 1))

   i=0

   while (seq_primes[i]**2)<b:

       j=i

       while seq_primes[j]<=(b/seq_primes[i]):

           sieve_set.discard(seq_primes[j] * seq_primes[i])

           j+=1

       i+=1

   return sorted(sieve_set)

primes = set(sieve_of_erastothenes(10000))

def prime_fibonacci(n):

   fib = []

   out = []

   fib.append(0)

   fib.append(1)

   fib.append(1)

   while fib[-1]<=n:

       print(fib[-1])

       fib.append(fib[-1]+fib[-2])

       if fib[-1] in primes:

           out.append(fib[-1])

   print(out)

prime_fibonacci(10000)