☰

» »

[Raptor] Razcep na prafaktorje

[Raptor] Razcep na prafaktorje

BeaTeX ::

Zna kdo narediti program v raptorju, ki število razcepi na prafaktorje?
  • spremenil: Mavrik ()

lebdim ::

malo pomisli, kako se v matematičnem smislu število razcepi na prafaktorje. to potem poskusi uporabiti ...

Math Freak ::

V Pythonu bi sprogramiral nekako tako:

def prafaktor(število): 
    seznam = []
    for indeks in range(2,število):
        while število % indeks == 0:
            seznam.append(indeks)
            število = število / indeks
    return seznam


Klic funkcije:
>>> prafaktor(245700)
[2, 2, 3, 3, 3, 5, 5, 7, 13]


Torej imamo neko število. Ustvarimo prazen seznam. V for zanki ustvarimo indeks, ki teče od 2 do tega števila. Dokler je število deljivo z indeksom, dodajamo indekse v seznam -> število se zmanjša na količnik pri deljenju števila z indeksom. Na koncu vrnemo seznam indeksov - prafaktorjev.

Zgodovina sprememb…

lebdim ::

@Math Freak,
kaj pa, kako bi modificiral ta programček, če bi hoteli, da programček izpiše faktorizacijo števila v potenčni obliki, npr. v obliki: 245700 = 22 * 33 * 52 * 7 * 13 ??

Math Freak ::

Dodaš samo še števec:

def prafaktor(število): 
    seznam = []
    števec = 0;
    for indeks in range(2,število):
        while število % indeks == 0:
            števec += 1
            število = število / indeks
        if števec > 0:
            seznam.append(str(indeks)+ "^" +str(števec))
        števec = 0
    return seznam


Klic:
>>> prafaktor(245700)
['2^2', '3^3', '5^2', '7^1', '13^1']

Math Freak ::

Lahko bi se še optimiziral program, tako da preverja samo liha števila - soda ne morejo biti praštevila in podobno. Samo za začetek - za manjša števila do par milijonov dela dosti hitro.

lebdim ::

aja, to pa itak ... kakšne kompleksnosti je tale algoritem - O(1) al O(n), glede na to, da imaš zanko?

Math Freak ::

Se mi je zdelo nekam čudno, da tako počasi deluje...

Popravek:
def prafaktor(število): 
    seznam = []
    števec = 0
    indeks = 2
    while indeks <= število:
        while število % indeks == 0:
            števec += 1
            število = število / indeks
        if števec == 1:
            seznam.append(str(indeks))
        elif števec > 1:
            seznam.append(str(indeks)+ "^" + str(števec))
        števec = 0
        indeks += 1
    return seznam


Izvedba: 
>>> prafaktor(107482873536)
['2^6', '3^6', '19', '29', '37', '113']


Range ni kot pri c#, še zmeraj je šel do konca - ni se sproti zmanjševal, kot sem mislil, da se bo. Zdj dela hitro tudi za velika števila.

Zgodovina sprememb…

Math Freak ::

Ta algoritem bo v najslabšem primeru preletel vsa števila od 1 do n s premikom 1, če je n praštevilo. Če bi implementiral, da pregleduje poleg dvojke samo liha števila, bi preletel največ polovico vseh števil (to je n/2).

čuhalev ::

Pa zanka naj gre le do SQRT(stevila).

Math Freak ::

Tocno, pozabil sm na to :).

Math Freak ::

@jaakaa

čuhalev je izjavil:

Pa zanka naj gre le do SQRT(stevila).


Samo če malo optimiziram kodo, tako da preverim najprej posebej 2 in nato liha števila (verjetno se da še naprej optimizirat, tako da ne preverjaš recimo deljenje z 9, če si preveril že s 3 in deljenje s 25, če si preveril deljenje s 5):

import math
import time

def prafaktor(število):
    zacetek = time.time();
    start_time = time.time()
    seznam = []
    števec = 0
    indeks = 3

    while število % 2 == 0:
        števec += 1
        število = število // 2
    if števec == 1:
        seznam.append(str(2))
    elif števec > 1:
        seznam.append(str(2)+ "^" + str(števec))

    števec = 0
        
    while indeks <= math.sqrt(število):
        while število % indeks == 0:
            števec += 1
            število = število // indeks
        if števec == 1:
            seznam.append(str(indeks))
        elif števec > 1:
            seznam.append(str(indeks)+ "^" + str(števec))
            
        števec = 0
        indeks += 2
    if število != 1:
        seznam.append(str(število))
    print("čas v sekundah: ", time.time()-zacetek)
    return seznam


Za ta del:
while indeks <= math.sqrt(število):


Potrebujemo toliko časa:
 >>> prafaktor(4822466496511903633758065207575071257)
čas v sekundah:  0.6845641136169434
['1299763', '1299791', '1299811', '1299817', '1299821', '1299827']


Če pa to zamenjamo z: 
while indeks <= število:


Potrebujemo toliko časa:
>>> prafaktor(4822466496511903633758065207575071257)
čas v sekundah:  0.42539095878601074
['1299763', '1299791', '1299811', '1299817', '1299821', '1299827']


Očitno potrebuje več časa za preračunavanje korenov, kot če pregledamo vsa števila.

Zgodovina sprememb…

čuhalev ::

Ja, koren je požrešna operacija, ampak vseeno se lahko pomikas le do stevilo/3, ker za delijivost z dva preveriš takoj. Ali pa najdes dober približek korena.

Randomness ::

Ne rabiš čarati s korenom, le pogoj "kvadriraš": 
while indeks <= math.sqrt(število)
spremeniš v 
while indeks*indeks <= število

Math Freak ::

Točno =), tudi na to sem pozabil.

Spet če preverim hitrost je ta metoda po hitrosti med obema prejšnjima. Če greš do števila še kar najhitreje prideš čez. Mogoče je samo za ta čuden primer, kjer so praštevila ogromna.

Math Freak ::

Če delim s 3, je ista zgodba. Ali je možno, da je množenje števil med sabo časovno dosti bolj potratno kot primerjanje? Ne vem v podrobnosti kako delujejo te zadeve.

Rokm ::

Od možnih variant zgoraj je seveda najhitrejsa :
while indeks <= število:


Upoštevati moraš da to število sproti deliš s prafaktorji ki jih prepoznas, zato index vedno pride samo do največjega prafaktorja (do korena prideš kadar razstavljas kvadrat praštevila, v ostalih primerih program konča prej). Ob prihodu do največjega faktorja in deljenju z njim število tako postane 1 in konča zanko.

V primeru:
while indeks <= math.sqrt(število)
while indeks*indeks <= število

tako uvedes dve operaciji (mnozenje in koren), ki sta v tem primeru predragi.

Ena izmed možnih izboljšav je da namesto indeksa uporabimo seznam praštevil (najhitreje izračunamo z Eratostenovim rešetom) in delimo samo z njimi -> Trial division @ Wikipedia. Ostale izboljšave pa potem zahtevajo malo globlje znanje matematike.

Randomness ::

Math Freak je izjavil:

Če delim s 3, je ista zgodba. Ali je možno, da je množenje števil med sabo časovno dosti bolj potratno kot primerjanje? Ne vem v podrobnosti kako delujejo te zadeve.

To gre v veliki meri na račun specifik programskega jezika Python3 in njegove implementacije tipa int.

Math Freak ::

@Rokm

Ja, prav imaš. Nisem se poglobil v ta problem, ker nisem imel časa, sem pa začel reševati probleme na Project Euler, kjer je optimizacija kode in pri drugih programskih jezikih tudi izbor tipa spremenljivk ključnega pomena. Hvala za info =).

stb ::

Lahko optimiziraš tudi tako, da koreniš le enkrat preden greš v zanko in potem primerjaš indeks s to konstanto, namesto da jo izračunavaš v vsakem ciklu.

Math Freak ::

Tud to sm probal, sam če prebereš post od Rokm - a: do tega korena ti nikoli ne prideš, razen če imaš praštevilo. Zmeraj se bo to število prej zmanjšalo, tako da nima smisla računat korena.

imagodei ::

A ni v primeru enega ali drugega od teh dveh pogojev:
while indeks <= math.sqrt(število)
while indeks*indeks <= število

tako, da program ob vsakokratni ponovitvi zanke preračuna koren oziroma množenje? Kaj pa, če bi to operacijo ponovil samo enkrat pred zanko, potem pa bi v pogoju zanke samo primerjal? Nekako takole:
meja = math.sqrt(število)
while indeks <= meja


EDIT: Ah, sem predolgo časa pisal odgovor, pa mi iz neznanega razloga ni osvežilo strani. Vidim, da ste to že obdelali.
- Hoc est qui sumus -

Zgodovina sprememb…

  • spremenil: imagodei ()

Math Freak ::

Ja, samo korena ne rabiš, ker se zanka skoraj zmeraj konča, preden sploh prideš do korena.

Zgodovina sprememb…

Rokm ::

V bistvu je tole brezveze testirati in primerjati le na enem primeru. Še posebej ker je ta primer izredno specifičen (zmnožek šestih zaporednih praštevil) in v tem primeru je vseeno ali delis vse do najvecjega faktorja ali do drugega najvecjega. Če bi pa poskušal faktorizirat 2*(veliko praštevilo) bi pa algoritem, ki je v prvem primeru najhitrejši bil počasnejši kot iskanje deljitelja do korena.

Math Freak ::

Vem, preveril sem tudi ostale primere. Vse je odvisno od inputa - zmnožek kolikšnih in kakšnih praštevil je število.

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Python - pomoč (strani: 1 2 3 )

Oddelek: Programiranje		10318142 (8890) black ice
»

Python

Oddelek: Programiranje		203049 (1735) d_DJ
»

Naloga iz Putka - UPM

Oddelek: Programiranje		242223 (1559) NejcSSD
»

[Python] Domači nalogi

Oddelek: Programiranje		333079 (1969) ragezor
»

Python, prosim za pomoc pri programiranju (strani: 1 2 3 )

Oddelek: Programiranje		10414056 (10158) lenika

Več podobnih tem