Cześć. Mam taki oto program do generowania liczb pierwszych i niestety nie chce mi działać. Właściwie to wypisuje mi tylko "1" w tablicy. Czy ktoś mógłby na to popatrzeć? ;)
def wyznacz_pierwsze(n):
pierwsze=[]
a=2
for i in range (2, n):
if a%i==0:
break
else:
pierwsze.append(a)
a+=1
pierwsze.insert(0,1)
return pierwsze
print(wyznacz_pierwsze(300))
Ten program sprawdza tylko podzielność przez 2, poprawny będzie np taki:
pierwsze = [2]
def czy_pierwsza(liczba):
for dzielnik in pierwsze:
if liczba % dzielnik == 0:
return False
if dzielnik * dzielnik > liczba:
return True
return True
def wyznacz_pierwsze(liczba):
for i in range(2, liczba):
if czy_pierwsza(i) is True:
pierwsze.append(i)
return
wyznacz_pierwsze(300)
print(pierwsze)
Co do```python
if dzielnik * dzielnik > liczba
Twój kod nie działa, wiadomo dlaczego. Potrzeba funkcji is_prime:
def is_prime(n):
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
limit = int(math.sqrt(n))
k = 1
while 6 * k - 1 <= limit or 6 * k + 1 <= limit:
if n % (6 * k - 1) == 0 or n % (6 * k + 1) == 0:
return False
k += 1
return True
To jest nieco ulepszona wersja naiwnego sprawdzania: https://en.wikipedia.org/wiki/Primality_test#Simple_methods.
Teraz można już jak wyżej:
def get_primes(n):
primes = []
for k in range(n):
if is_prime(k):
primes.append(k)
return primes
Wydajniej będzie za pomocą generatora: https://docs.python.org/3/howto/functional.html#generators
def get_primes_gen(n):
while True:
if is_prime(n):
yield n
n += 1
Nie Musisz ich teraz pakować naraz do listy, tylko pobrać ile Chcesz z generatora, na przykład iterując go w pętli czy używając metod (opisane w linku).
Sa też specjalne algorytmy do generowania liczb pierwszych, na przykład Sito Erastotenesa: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
import math
def erastotenes_sieve(n):
arr = [True] * n
limit = int(math.sqrt(n)) + 2
for i in range(2, limit):
j = i**2
k = 0
while j < n:
arr[j] = False
k += 1
j = i**2 + k * i
out_val = []
for m in range(2, len(arr)):
if arr[m] == True:
out_val.append(m)
return out_val
Jak na Pythona to nawet, znajduje primes do 100 milionów w 32.5 sek.
Liczenie pierwiastka czyli Math.sqrt() tylko spowolni program, przy pierwszych nie warto go stosować. swoją drogą w Pythonie można tworzyć funkcję wewnątrz funkcji. Dzięki czemu możesz zrobić tak:
def wyznacz_pierwsze(liczba):
pierwsze = [2]
def czy_pierwsza(liczba):
for dzielnik in pierwsze:
if liczba % dzielnik == 0:
return False
if dzielnik * dzielnik > liczba:
return True
return True
for i in range(2, liczba):
if czy_pierwsza(i) is True:
pierwsze.append(i)
return pierwsze
print(wyznacz_pierwsze(300))
Dla liczby 10**6 na moim sprzęcie bez jit'a.
next_test_pr (in sec): 0.03993 # 98.7257% faster than the slowest
lion_primes (in sec): 3.13345 # The slowest
def next_test(n=10**6):
if n < 100: return [i for i in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) if i<n];
res = [2]; s = bytearray([0]); i = 3; j = 9;
nxt_i = lambda: i+2; nxt_j = lambda: i*i;
s *= n
def mo():
s[j::i+i] = bytearray([1])*int((n-(j))/(i+i)+1)
res.append(i)
while j<n:
mo() if not s[i] else None
i = nxt_i(); j = nxt_j();
return res + [g for g in range(i, n, 2) if not s[g]]
Co prawda można jeszcze szybciej z jeszcze mniejszym zużyciem pamięci wykorzystując cythona, ale to już powinno być wystarczająće, ale może ci posłuży mój algorytm ;p.
Najważniejsze tutaj to operować na fragmentach list, bo to potrafi ponad dziesięciokrotnie zoptymalizować program. (Srry za nie pythonowy zapis, ale na slajdzie musiało mi się zmieścić :)
@Edit: Takie wtrącenie co do sita euklidesa.
Na generator to łatwo przerobić, tylko wrzucasz inicjalizację w klasie dla wybranego przez siebie zakresu ;p.