Da sa lepsie ? Overovac, generator prvocisel. Python 3.

Proč si ukládáš nalezená prvočísla, když je pak nepoužíváš pro kontrolu dalších čísel?

Preco sa zase nezaoberate mojim dotazom ale svojim vlastnym ?

Ptal ses, jak to napsat lépe, aby to bylo rychlejší. No ale vidím, že umíš jenom prskat kolem sebe a o radu ve skutečnosti nestojíš.

Nie, ty si nepochopil celkovy dotaz alebo zase necitas pozorne.
OVEROVAC cisel ci je zadane cislo prvocislo. To mam, nic dalsie s tym nechcem robit, ale sa pytam, ci sa to da napisat lepsie !?

Dalsi skript je GENERATOR prvocisel z celkoveho range cisel. To tiez funguje tak ako chcem, len sa pytam na to co som sa pytal.

TAK PRECO mi nasilu nukas dalsie operacie co ma nezaujimaju ???

Ale já ti napsal, jak to napsat lépe. Použití už jednou nalezených prvočísel celý proces mnohonásobně urychlí.

Ozaj nechapem, ved ja som to napisal najlepie ako som vedel. Nic sa tam neopakuje. Pred hlavnou narocnou brute force detekciou pomocou odmocniny, som predtym napisal co najviac vyradovacich kol, aby sa pracovalo s co najmensim poctom cisel.

Skus mi to este inac vysvetlit. Najlepsie konkretne ktore riadky.
Skusal si vobec tie skripty ?

Dik

Právě ta brute force detekce je největší brzda. Procházíš tam všechna čísla od num až do odmocniny z num. Přitom by stačilo procházet pouze už nalezená prvočísla menší či rovné odmocnině z num.

Neviem ako sa dajú písať skripty v Pythone lepšie, ale zrejme ten Tvoj algoritmus nestojí za veľa...

Takto to vyzerá na mojom PC (AMD Athlon II X4 630 - 2,8GHz):

Program aj s algoritmom napísaný v DELPHI, skompilované ako 64-bit aplikácia...

Optimalizacia sa robi bud optimalizaciou algoritmu, alebo optimalizaciou vnutornych cykov, alebo napisanim to v niecom low level. Prva vec viz Wikan, druha vec zbytocne milionkrat v cykle testujes 2,3,5 to snad staci raz pred cyklom, prevadzas tam cisla na stringy (OMG), pouzivaj len delenie a nic neprevadzaj na stringy, delenie je 1 alebo par CPU clockov. Prevod na string je trilion clockov. Cele to je nezmysel. A ten treti bod, da sa to napisat v assembleri, potom to bude optimalne.

P.S. stringy budes potrebovat az ked sa to cislo nezmesti do 64bitov apod, ale to zas nemozes prevadzat zo ziadneho "num", ptz sa to potom ako cislo vobec ulozit neda, a je nutne to drzat v stringu od zaciatku

A je logicke ze ked do najvnutornejsieho cyklu ktory sa vykonava trilionkrat a v ktorom je defakto len par deleni (par CPU cyklov) strcis volanie nejakej process_time fcie ktora potrebuje trilion CPU cyklov, tak to bude trvat o polovicu dlhsie. Navyse to volanie tam je este aj zbytocne.

Alebo

                elif numb % 2 == 0:             # evens excluded
                    continue  
                elif num % numb == 0:           # not prime
                    break                    

co to je za blbost? Ked jedno delenie num % numb trva cas X, a vies s nim priamo overit ze ci to je prime, tak naco tam strkas pred to zbytocnu operaciu numb % 2, takto ti to trva cas 2*X t.j. 2*dlhsie. Optimalizacia je o ZMENSOVANI poctu operacii, a ne o zvacsovani. Ked chces preskakovat parne cisla tak sa to da robit rovno v cykle ze sa robi cislo+2, a ne cislo+1. Jak sa to robi v tom python scripte si najdi sam, ja take neoptimalne veci nepouzivam.

Pre poriadok. Toto je povodny vytvor s casom 40 s, pri inpute 999999.
05QDZEX

@ Wikan:
Upravil som to podla tvojej rady nasledovne:
0946RQM
Ale cas sa vysplhal uplne inde. Po vyse 2 minutach som to zrusil.

@ pme:
Mam takyto CPU: 2 jadrovy: Intel(R) Core(TM)2 Duo CPU P8400 @ 2.26GHz
Ale aj mne sa zda, ze to trva akosi dlho.

@ MM..:
Na stringy musim previest koncovu cislicu cisla, lebo int sa neda indexovat ani iterovat, neni subscriptable. To iste plati pri sucte cifier cisla.

Inak sa koniec casomeracu neda umiestnit, aby som sa vyhol list.append().

"Ked jedno delenie num % numb trva cas X, a vies s nim priamo overit ze ci to je prime, tak naco tam strkas pred to zbytocnu operaciu numb % 2, takto ti to trva cas 2*X t.j. 2*dlhsie. Ked chces preskakovat parne cisla tak sa to da robit rovno v cykle ze sa robi cislo+2"
- Upravil som povodny vytvor a teda toto:

            for numb in range(int(num ** 0.5) + 1):  # square root brute force check
                if numb < 7:
                    continue
                elif numb % 2 == 0:             # evens excluded
                    continue  
                elif num % numb == 0:           # not prime
                    break                    
            else:
                list_of_primes.append(num)

som nahradil tymto:

            for numb in range(7, int(num ** 0.5) + 1):  # square root brute force check
                if num % (numb + 2) == 0:               # not prime, evens excluded
                    break                    
            else:
                list_of_primes.append(num)

a usetrilo sa 5 sekund :)

Tohle vypadá divně:

                if num % element == 0:           # already found primes scan
                    break
            else:
                list_of_primes.append(num)

Nepřidává to náhodou do toho seznamu všechna čísla a ne pouze prvočísla?

Nie, je to v poriadku.
Pozeral som to tuto krok za krokom.
Chod sem: visualize.html
Pastni tam ten kod bez casomeraca: 2HA1M3M
Daj input: 100 a pekne to ide ako ma.

Zkusil jsem tohle: 07MHFHV
Chodí to docela rychle, ale pořád je místo pro optimalizace.

Nemusis nic prevadzat na string. testovanie prvocisel je jedno delenie v cykle. NIC VIAC v tom cykle nema byt. TO je najoptimalnejsie. (a cyklus ma mat krok 2).
P.S. az prestanes pouzivat integery uplne (vyssi level co sa tyka velkosti cisla) tak potom je to nieco uplne ine. Ak sa len hras ze pouzivas integery tak nerob ziadne somariny vnutri cyklu a ani nic neprevadzaj na stringy.

Mozes cely post rozpisat ako si to myslel ? Nechytam sa vobec

Vyhod vsetky prevody na string a vsetky nezmysly ktore ten string pouzivaju.

a dalej ? to riesenie som chcel precitat normalnejsie

ako vysvetlis, ze optimalnejsie riesenie Wikanove, zabera viac casu ?

Ja neviem co robi Wikanove riesenie necital som to, ale ty robis blbo uplne vsetko.

upravene "tvoje" riesenie (bez vyuzivania doterajsieho zoznamu prvocisel)

user_input = int(input('Write number for all primes up to(included): '))
list_of_primes = []
from time import process_time
t = process_time()

#BLBOSTI VON Z CYKLU
if user_input >= 2:
        list_of_primes.append(2)
if user_input >= 3:
        list_of_primes.append(3)
if user_input >= 5:
        list_of_primes.append(5)

num = 7
while num <= user_input:   #PRVY CYKLUS BEZ BLBOSTI
        numb = 3
        konec = (num ** 0.5) + 1
        while numb <= konec:  #DRUHY CYKLUS BEZ BLBOSTI
            if num % numb == 0:           # not prime
                    break 
            numb = numb + 2   # KROK DVA
        else:
            list_of_primes.append(num)
        num = num + 2         # KROK DVA

neviem ci to je syntakticky spravne nepoznam python. Toto trva kolko?

ok dik len pockaj chvilu, zistil som ze to wikanove riesenie asi bude rychlejsie(prepac wikanko. aj ked asi nie o vela, lebo vypadne len par cisel), len ja som zabudol zadat limit hornej hranice.
malo to byt takto:

        else:
            summ = 0
            for element in list_of_primes[3:list_of_primes.index(int(num ** 0.5))]:  # start from prime 7
                if num % element == 0:                                               # already found primes scan
                    break
            else:
                list_of_primes.append(num)

lenze mi vyhadzuje chybu, ked kontroluje cislo 17.
lebo odmocnina je 4 a to nie je v nasom liste prvocisel. tuto list.index(value) metodu potrebujem upravit, ze ked nenajde presne to cislo, tak nech zoberie najblizsie nizsie prvocislo. lenze, do indexu nemozem dat boolean, lebo vyjde nie cislo ale True alebo False. teraz neviem co spravit

Nedavaj tam ziadne indexy, kontroluj cely list. A vyhod tie tvoje nezmyselne extra kontroly na 2,3 a 5, ved to predsa je v tom liste to iste (kontrola na 2, 3 a 5 je hned ako prva, v zozname prvocisel, nemusis to predtym kontrolovat extra debilnymi stringami)

wikan:

nie je mozne to ohranicit indexom, lebo ciselny gap medzi prvocislami je random. neda sa to spravit.

tak som to vymyslel takto:

            for element in list_of_primes: 
                if element <= int(num ** 0.5): 
                    if num % element == 0:                                               # already found primes scan
                        break

lenze uz pri malom inpute: 99999, to trvalo 47 sekund !

nechapem ako je to mozne, ked logicky, tymto prechadzam mensim poctom cisel ako tomu bolo tu:

            for numb in range(7, int(num ** 0.5) + 1):  # square root brute force check
                if num % (numb + 2) == 0:               # not prime, evens excluded
                    break                    

uz neviem co s tym

Já ale o indexech nic nepsal. Proč jsi nepoužil to mé řešení?
A pomalé je to proto, že tam neustále počítač odmocninu, což oproti ostatním operacím trvá celou věčnost.

ved som pouzil - prechadzal som uz ulozene prvocisla ako si povedal

a prave som zistil ze to o 5 sekund rychlejsie MM.. riesenie nepocita spravne.
toto naslo ako prvocislo: 99967, ale nie je
male cisla malo spravne, myslel som si ze je to v poriadku

uz ma to prestava bavit toto programovanie..

Myslím přímo ten kód, který jsem sem dával.

Aha, nevsimol som si to.
Tak pri 999999 to trvalo 8-9 sekund, teda dost mega efektivne. Hlava mi to nebere.
Nakolko nemam rad, ked vsade lietaju variabilne zbytocne definovane, tak som ti zrusil 'maximum' a napisal som to priamo do kodu:

povodne:

for num in our_range:
    maximum = num ** 0.5
    for prime in list_of_primes:
        if prime > maximum:
            list_of_primes.append(num)
            break
        if num % prime == 0:
            break
print(list_of_primes)

prerobene:

for num in our_range:
    for prime in list_of_primes:
        if prime > num ** 0.5:
            list_of_primes.append(num)
            break
        if num % prime == 0:
            break
print(list_of_primes)

takto prerobene to trvalo 14-15 sekund. nechapem preco

To tam neni zbytecne, ale prave proto, aby se to nepocitalo znovu pri kazdem pruchodu.

MM.. mi hore napisal, ze kazde druhe cislo overovat, ze sa da priamo v cykle. a neda sa. teraz to kukam vo vizualizeri, a vobec neberie do uvahy tuto linu:

                if num % (numb + 2) == 0:               # not prime, evens excluded

stale berie numb a nie numb+2
preto to pocita hovadiny, ale ako je potom mozne ze aj tak to preslo o 5 sekund rychlejsie ?

prosimta, co to tam zas lepis za nezmysel? Ja som nikde nepisal ze mas delit nieco s numb+2. A dal som ti jasne priklady jak sa to robi. Nepochopil si ani slovo, uz radsej nic neprogramuj :)