Jakiś czas temu na grupie matematycznej na FB ktoś wrzucił algorytm który z dużą dokładnością jest w stanie policzyć kolejne liczby pierwsze. Problem w tym że ten wzór jest rekurencyjny...
Watpie zeby taka implementacja była szybsza niż sprawdzenie każdej n'ki przy użyciu sqrt(n). W końcu, najpierw musimy wyznaczyć tablicę, co według wikipedii zajmuje O(N log (log N). Potem musimy jeszcze przejść tablicę liczb pierwszych by sprawdzić czy n'ka się w niej znajduje, czyli praktycznie zlozoność liniowa (keyword in przechodzi przez wszystkie elementy). Lepiej byłoby zwrócić tablicę numbers i sprawdzić czy na indeksie n-1 mamy True.
jest szybsza i to o wiele, zrobiłem zbadanie każdej liczby do 7000000 metodą isprime() i sito(), isprime zabiera około 2 i pół minuty a sito zaledwie sekunde
to git, ale wydaje mi sie ze mozna jeszcze przyspieszyc implementacje lewusa robiac tablice o dlugosci n gdzie na odpowiednim indeksie bedzie dana liczba i wartosc True jezeli jest ona pierwsza. Wtedy gdy chcemy sprawdzic czy liczba jest pierwsza nie trzeba liniowo przesukiwac tablicy tylko po prostu dac nasza liczbe jako indeks
@@kw4794 można ale wiesz to bardziej pod mature na zapamiętanie na szybko, jeżeli w pare sekund ci wyrzyga wynik to jest git. Jeżeli potrzebujesz faktycznie liczb pierwszych do jakiegos programu to mozna kombinowac z optymalizacją jak mówisz
@@kw4794 bo jakbyśmy optymalizowali każdy kod na tą mature to wyobraź sobie pisać merge sorta zamiast bubblesorta jakby prosili o posortowanie tablicy (nie prosza o sortowanie o złożnosci O(logn), to jest troszeczke za dużo linii i myślenia, a efekt taki sam
Skończyłem na zabawie z sitem i pierwszymi w Pythonie, jak doszedłem do zapisu do plików na dysku liczb pierwszych od 0 do 1mld w 4s. Nic nowego nie wymyślę xD
Napisałem ci komentarz, że twój program nie jest do końca poprawny, ponieważ jeżeli podana liczba n jest liczbą pierwszą, twoje sito jej nie zawrze w swojej liście, a sito erastotenesa ma wyznaczyć wszystkie liczby pierwsze od 2 do n włącznie i żeby to naprawić, trzeba by zamiast n, dać n+1 def primes_list(n): numbers = [True for _ in range(n+1)] primes = [] for i in range(2, n+1): if i
Dzięki za film! Genialnie to tłumaczysz, proszę, rób więcej algorytmiki!
Ja osobiście do funkcji prime używam pętli while i warunek d*d
Jakiś czas temu na grupie matematycznej na FB ktoś wrzucił algorytm który z dużą dokładnością jest w stanie policzyć kolejne liczby pierwsze. Problem w tym że ten wzór jest rekurencyjny...
aha
giga zajebisty filmik PZDR.
😅I pomyśleć ze lewus nauczył mnie więcej programować przez 20 minut niż cały rok w szkole
nooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
żeby pisać to no trzeba się namęczyć(bo trzymanie spacji nie działa)!!!
Watpie zeby taka implementacja była szybsza niż sprawdzenie każdej n'ki przy użyciu sqrt(n). W końcu, najpierw musimy wyznaczyć tablicę, co według wikipedii zajmuje O(N log (log N). Potem musimy jeszcze przejść tablicę liczb pierwszych by sprawdzić czy n'ka się w niej znajduje, czyli praktycznie zlozoność liniowa (keyword in przechodzi przez wszystkie elementy). Lepiej byłoby zwrócić tablicę numbers i sprawdzić czy na indeksie n-1 mamy True.
jest szybsza i to o wiele, zrobiłem zbadanie każdej liczby do 7000000 metodą isprime() i sito(), isprime zabiera około 2 i pół minuty a sito zaledwie sekunde
to git, ale wydaje mi sie ze mozna jeszcze przyspieszyc implementacje lewusa robiac tablice o dlugosci n gdzie na odpowiednim indeksie bedzie dana liczba i wartosc True jezeli jest ona pierwsza. Wtedy gdy chcemy sprawdzic czy liczba jest pierwsza nie trzeba liniowo przesukiwac tablicy tylko po prostu dac nasza liczbe jako indeks
@@kw4794 można ale wiesz to bardziej pod mature na zapamiętanie na szybko, jeżeli w pare sekund ci wyrzyga wynik to jest git. Jeżeli potrzebujesz faktycznie liczb pierwszych do jakiegos programu to mozna kombinowac z optymalizacją jak mówisz
@@kw4794 bo jakbyśmy optymalizowali każdy kod na tą mature to wyobraź sobie pisać merge sorta zamiast bubblesorta jakby prosili o posortowanie tablicy (nie prosza o sortowanie o złożnosci O(logn), to jest troszeczke za dużo linii i myślenia, a efekt taki sam
wszystko fajnie dopóki matura z operonem nie powiedziała kiedyś: znajdź liczby pierwsze z zakresu od 1 do 10^9, wtedy python wysiadał
Ogólnie każdy arkusz jest tak układany, że jego autorzy wydają się faworyzować c++ nad Pythona
@@bartekgawe2539 no i bardzo dobrze, sztywne gity kodują w c
Więcej algorytmiki 🙌
Skończyłem na zabawie z sitem i pierwszymi w Pythonie, jak doszedłem do zapisu do plików na dysku liczb pierwszych od 0 do 1mld w 4s. Nic nowego nie wymyślę xD
git przyda sie
nie chciałbyś zrobić algorytmiki pod maturę z informatyki?
ale mam ogar🤓
za odkrycie zasady kolejności liczb pierwszych jest nagroda 1000000 dolarów
Zrób filmik o liczeniu pola pod wykresem całki
no jak masz wykres i liczysz całkę z tego wykresu, to masz pole pod wykresem xD
kumaci ogarnęli że pierwsza animacja w tle jest w manim
czytałem ten kod, 3blue1brown ma 300 iq
druga też
Napisałem ci komentarz, że twój program nie jest do końca poprawny, ponieważ jeżeli podana liczba n jest liczbą pierwszą, twoje sito jej nie zawrze w swojej liście, a sito erastotenesa ma wyznaczyć wszystkie liczby pierwsze od 2 do n włącznie i żeby to naprawić, trzeba by zamiast n, dać n+1
def primes_list(n):
numbers = [True for _ in range(n+1)]
primes = []
for i in range(2, n+1):
if i
Dlaczego 77+33 to nie jest 100💀
liczba 2137 jest liczba pierwsza :D
sqrt czyta się skuert
pierwszy komentarz>