Znajdowanie liczb pierwszych¶

Ćwiczenie 1 – liczba dzielników¶

Napisz funkcję ile(n), której wynikiem jest liczba dzielników liczby n podanej jako parametr.

W rozwiązaniu jest błąd, czy umiesz go znaleźć.

def ile(n): licznik = 0 for i in range(1, n+1): if n % i == 0: licznik += licznik + 1 # print(i) return licznik print(ile(6))

Wersja szybsza, ale trochę bardziej skomplikowana.

from math import sqrt def ile(n): licznik = 0 for i in range(1, int(sqrt(n))+1): if n % i == 0: licznik += 1 # print(i) if sqrt(n)*sqrt(n) == n: return 2*licznik - 1 else: return 2*licznik print(ile(6))

Jeśli chcemy sprawdzić, czy liczba jest pierwsza, wystarczy zbadać, czy nie dzieli się przez kolejne liczby od 2 do n-1.

Ćwiczenie 2 – badanie, czy liczba jest pierwsza¶

Napisz funkcję czy_pierwsza(n), której wynikiem jest True, gdy liczba jest pierwsza oraz False w przeciwnym przypadku.

def czy_pierwsza(n): for i in range(2, n): if n % i == 0: return False return True print(czy_pierwsza(12)) print(czy_pierwsza(13))

A jak będzie wyglądać wersja szybsza?

def czy_pierwsza(n): pass print(czy_pierwsza(12)) print(czy_pierwsza(13))

Ćwiczenie 3 – wykreślanie wielokrotności¶

Napisz funkcję wykresl(a, n), której wynikiem jest lista złożona z 0 i 1. Jeśli liczba ta jest wielokrotnością a, to na jej miejscu powinna być wartość 0, w przeciwnym przypadku 1.

Obecnie funkcja działa tylko dla liczby 3. Zmodyfikuj ją tak, aby działała ogólnie dla a.

def wykresl(a, n): # generowanie listy długości n złożonej z 1 lista = [1 for i in range(n+1)] # wykreślanie wielokrotności for i in range(3, n+1, 3): lista [i] = 0 #pomijamy 0 return lista[1:] print(wykresl(2, 10)) print(wykresl(3, 15))

Ćwiczenie 4 – znajdowanie liczb pierwszych¶

Napisz funkcję sito(n), której wynikiem jest lista liczb pierwszych do n włącznie.

def sito(n): kandydat = [1 for x in range(n+1)] pierwsze = [] for i in range(2,n+1): if kandydat[i] != 0: pierwsze.append(i) for j in range(i+i,n+1,i): kandydat[j]=0 return pierwsze print(sito(10)) print(sito(17))