Plocka fram alla primtalsfaktorer
Kära Nemesis och er tjänare har nyligen promenerat i primtalsängar med följande spännande problem.
Vår kod är att hitta faktor och reducera inputen vid varje steg. Finns det en sätt att lösa det utan att dela tal med alla möjliga faktorer? Dvs, vad är den mest effektiva sätt att plocka fram primtal?
Din kod är ganska bra och väldigt läsbar. Man kan ordna så man inte behöver utföra sqrt(number) varje varv utan bara när den ändras.
Om man tar reda på alla intressanta primtal först så behöver man inte prova sammansatta faktorer. Ett bra sätt att ta reda på alla primtal upp till en viss gräns är Eratosthenes' såll.
Detta problem tar bara en tal, så sqrt(tal) körs bara en gång.
Jag har en gammal Eratosthenes stal som ligger i mina sparade filar :). Men jag kunde inte generera arrayen av primtal i detta problem. Körtid är bara en sekund, generarar jag en primtal array går jag övertid och får error Time Limit Exceeded.
Menar du att det går snabbare att spara en fast kodad array för alla problem som har med primtal att göra, än att testa såhär med i?
(jag hoppas du förstår vad jag menar, jag är skittrött...)
sqrt(number) evalueras varje varv i loopen. Och det är bra, för annars skulle man testa mycket i onödan.
För att veta vilken som är snabbast av din metod, såll+loop och färdig primtalstabell + loop måste man nog provköra.
Aha isf kan jag skapa en konstant innan. Jag visste inte att det skulle omberäknas varje gång loopen körs!
Okej, tack för tipsen, ska testa det.
(..Det är nog snabbare med en färdig sammansätt array tycker en)
Nu läste jag kraven också. X kan vara upp till 109, så vi behöver primtal upp till ca 30000. Har du fått godkänt på den?
Ja, jag fick godkänt. 10^9 ryms i en int.
dajamanté skrev:Ja, jag fick godkänt. 10^9 ryms i en int.
Jag provkörde lite med och utan såll. Det verkar som om såll inte lönar sig för ett eller två tal som ska faktoriseras (men på min inte helt nya dator gick det ändå under en sekund), men med tre eller fler lönar det sig.
Länka din kod!
dajamanté skrev:Länka din kod!
You asked for it. https://pastebin.com/uRzGyKP4
tack!
Är det python?
dajamanté skrev:tack!
Är det python?
Ja.
