dajamanté är nöjd med hjälpen!
dajamanté 5228
Postad: 2 feb 2019

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?

Laguna 4372
Postad: 2 feb 2019

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.

dajamanté 5228
Postad: 2 feb 2019

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...)

Laguna 4372
Postad: 2 feb 2019

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.

dajamanté 5228
Postad: 2 feb 2019

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)

Laguna 4372
Postad: 3 feb 2019

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?

dajamanté 5228
Postad: 3 feb 2019

Ja, jag fick godkänt. 10^9 ryms i en int.

Laguna 4372
Postad: 3 feb 2019
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.

dajamanté 5228
Postad: 3 feb 2019

Länka din kod!

Laguna 4372
Postad: 4 feb 2019 Redigerad: 4 feb 2019
dajamanté skrev:

Länka din kod!

You asked for it. https://pastebin.com/uRzGyKP4

dajamanté 5228
Postad: 4 feb 2019

tack!

Är det python?

Laguna 4372
Postad: 4 feb 2019
dajamanté skrev:

tack!

Är det python?

Ja.

Svara Avbryt
Close