Primtal
Ett tal är en produkt av två ungefär lika stora primtal. En metod att faktorisera och hitta primtalsfaktorerna är att prova att dela med olika tal som är mindre än det ursprungliga talet.
Om det tar 1 min för en viss dator att faktorisera ett tal av ovanstående typ med 20 siffror med hjälp av oavanstående metod. Uppskatta hur lång tid det skulle ta att faktorisera ett tal med 40 siffror.
Jag tänker att det borde ta ungefär dubbelt så lång tid men jag vet att det med största sannolikhet är fel svar. Men bör det inte finnas ungefär lika många primal mellan 0 till ett tal med 20 siffror, som från det talet upp till ett tal med 40 siffror? Hur ska man tänka?
Hej och välkommen till Pluggakuten Andno!
Metoden går ut på att pröva alla tal som är mindre än det aktuella talet.
Den tid det tar är då linjärt beroende av antalet tal som är mindre än det aktuella talet, inte hur många siffror talet innehåller, inte heller hur många primtal det finns som är lägre än talet själv.
Exempel:
Talet 9 har 1 siffra och 8 (positiva hel)-tal som är mindre än talet.
Talet 99 har 2 siffror (dubbelt så många), men hela 98 (positiva hel)-tal som är mindre än.talet.
98 är mer än dubbelt så stort som 8, så.det skulle ta mer än dubbelt så lång tid att testa om 99 är ett primtal som att testa om 9 är det.
Riktigt så enkelt är det inte. Jag är själv inte säker på mitt resonemang i detta inlägg men jag tänker som följer. Enligt primtalssatsen så gäller det att om du väljer ett tal så finns det ungefär st primtal under det talet. Om du t.ex. väljer
Så får du att
Mellan tal som innehåller 0 till 20 siffror finns det alltså ca primtal och mellan tal som innehåller 0 till 40 siffror finns det cirka primtal. Alltså måste antalet primtal för tal med siffror mellan 20 och 40 vara differensen mellan dessa, alltså
Förhållandet mellan dessa primtals antal är Det finns alltså så många fler primtal mellan tal som har siffror mellan 20 till 40 än tal som har siffror mellan 0 till 20. Sen kan man ju spekulera och säga att tiden (1 min) då borde multipliceras med detta tal men alla primtal tar ju inte lika lång tid att faktorisera så det går ju inte.
Ett tillägg till Yngves inlägg: Det räcker att prova alla tal som är mindre än roten ur det aktuella talet.
Om 1 < n < 10 så kan man skriva
Lirim.K skrev :Riktigt så enkelt är det inte. Jag är själv inte säker på mitt resonemang i detta inlägg men jag tänker som följer. Enligt primtalssatsen så gäller det att om du väljer ett tal så finns det ungefär st primtal under det talet. Om du t.ex. väljer
Så får du att
Mellan tal som innehåller 0 till 20 siffror finns det alltså ca primtal och mellan tal som innehåller 0 till 40 siffror finns det cirka primtal. Alltså måste antalet primtal för tal med siffror mellan 20 och 40 vara differensen mellan dessa, alltså
Förhållandet mellan dessa primtals antal är Det finns alltså så många fler primtal mellan tal som har siffror mellan 20 till 40 än tal som har siffror mellan 0 till 20. Sen kan man ju spekulera och säga att tiden (1 min) då borde multipliceras med detta tal men alla primtal tar ju inte lika lång tid att faktorisera så det går ju inte.
Tack för ditt svar, lärde mig nått nytt!
Du skrev: men alla primtal tar ju inte lika lång tid att faktorierna så det går ju inte. Förstod inte riktigt vad du menade med att det olika lång tid att faktorierna alla primtal. Kan man inte tänka att det tar lika lång tid att dela ett tal med ett annat tal, även om det talet är ett primtal?
För om vi vet antalet primtal mellan 0 till talet x med 20 siffror, så vet vi ju att det tog 1 min att prova att dela talet x med samtliga primtal. För så fort vi har lyckats delat talet x med ett primtal där resultatet är ett nytt primtal så har vi ju båda primtalsfaktorerna: faktorn vi delar med och resultatet som är den andra faktorn (exempelvis om x för enkelhetsskull är 6 så får vi 6/2=3, alltså har vi 6=2*3 där både 2 och 3 är primtal). Eller tänker jag fel?
Yngve skrev :Hej och välkommen till Pluggakuten Andno!
Metoden går ut på att pröva alla tal som är mindre än det aktuella talet.
Den tid det tar är då linjärt beroende av antalet tal som är mindre än det aktuella talet, inte hur många siffror talet innehåller, inte heller hur många primtal det finns som är lägre än talet själv.
Exempel:
Talet 9 har 1 siffra och 8 (positiva hel)-tal som är mindre än talet.
Talet 99 har 2 siffror (dubbelt så många), men hela 98 (positiva hel)-tal som är mindre än.talet.
98 är mer än dubbelt så stort som 8, så.det skulle ta mer än dubbelt så lång tid att testa om 99 är ett primtal som att testa om 9 är det.
Hej, tack!
Ja, det är helt sant, tänkte nog inte riktigt till där. Dock försåt jag ändå inte riktigt hur jag ska kunna besvara frågan exakt när jag inte vet vad talen är exakt. Är det meningen att man bara ska ta två tal, ett med 10 siffror och ett med 20 siffror? Eller ska man ge ett mer generellt svar utan att göra ett antagande om vad de två talen är exakt?
SvanteR skrev :Ett tillägg till Yngves inlägg: Det räcker att prova alla tal som är mindre än roten ur det aktuella talet.
Om 1 < n < 10 så kan man skriva
n*1039=n*1020*1019=1020*n*1019=1010*n*1019
Jo men uppgiften handlar om den metoden som angavs, nämligen
En metod att faktorisera och hitta primtalsfaktorerna är att prova att dela med olika tal som är mindre än det ursprungliga talet.
Jag tolkar det som att algoritmen för att avgöra om talet n är ett primtal är en brute force-algoritm som prövar sig igenom delbarheten med alla positiva heltal mindre än n.
Jag tror att uppgiften vill belysa att trots att datorernas beräkningskapacitet numera är stor och billig så är den ändå inte vare sig obegränsad eller gratis och det är därför viktigt att förbereda beräkningsuppgifterna med hjälp av smarta algoritmer innan man låter datorerna ta över själva utförandet.
Andno skrev :Yngve skrev :Hej och välkommen till Pluggakuten Andno!
Metoden går ut på att pröva alla tal som är mindre än det aktuella talet.
Den tid det tar är då linjärt beroende av antalet tal som är mindre än det aktuella talet, inte hur många siffror talet innehåller, inte heller hur många primtal det finns som är lägre än talet själv.
Exempel:
Talet 9 har 1 siffra och 8 (positiva hel)-tal som är mindre än talet.
Talet 99 har 2 siffror (dubbelt så många), men hela 98 (positiva hel)-tal som är mindre än.talet.
98 är mer än dubbelt så stort som 8, så.det skulle ta mer än dubbelt så lång tid att testa om 99 är ett primtal som att testa om 9 är det.
Hej, tack!
Ja, det är helt sant, tänkte nog inte riktigt till där. Dock försåt jag ändå inte riktigt hur jag ska kunna besvara frågan exakt när jag inte vet vad talen är exakt. Är det meningen att man bara ska ta två tal, ett med 10 siffror och ett med 20 siffror? Eller ska man ge ett mer generellt svar utan att göra ett antagande om vad de två talen är exakt?
Du ska inte svara exakt. Det står att du ska göra en uppskattning av hur lång tid det kan ta.
Välj ett tal med 40 siffror, till exempel 1*10^39 och ett tal.med 20 siffror, till exempel 1*10^19.
Hur många gånger större är det 40-siffriga talet än det 20-siffriga talet?
Denna faktor kan du sen använda för att beräkna uppskattad datortid.
Du kan även experimentera med intervall.
Ta då ett så stort 40-siffrigt tal.som möjligt och jämför med ett så litet 20-siffrigt tal som möjligt.
Gör sedan tvärtom, ta ett så litet 40-siffrigt tal som möjligt och jämför med ett så stort 20-siffrigt tal som möjligt.
Ditt svar kan sedan använda dessa kvoter som bas för en max/min-uppskattning
10^20 är antalet test för ett fyrtiosiffrigt tal. 10^10 är antalet test för ett tjugosiffrigt tal. Eftersom 10^20 är 10^10 gånger så stort som 10^10, hur många sekunder tar det då? (Lirim.K skrev något om att faktorisera primtal. Det går inte.)
Vet inte varför jag skrev primtal där, menade bara "tal".
Henrik Eriksson skrev :10^20 är antalet test för ett fyrtiosiffrigt tal. 10^10 är antalet test för ett tjugosiffrigt tal. Eftersom 10^20 är 10^10 gånger så stort som 10^10, hur många sekunder tar det då? (Lirim.K skrev något om att faktorisera primtal. Det går inte.)
Så tolkar inte jag metodbeskrivningen.
Jag tolkar den som att antalet test skulle vara lika stort som talet själv minus ett.
En metod att faktorisera och hitta primtalsfaktorerna är att prova att dela med olika tal som är mindre än det ursprungliga talet.
Men det spelar nog inte så stor roll egentligen, det viktigaste är att du Andno gör en tolkning av problembeskrivningen och tydligt anger den innan du redovisar din lösning.
Typ så här:
Jag tolkar problemformuleringen på följande sätt: "Metoden att faktorisera och hitta primtalsfaktorer till ett tal n går ut på att ...(din tolkning)... Om så är fallet så gäller att ...(ditt resonemang och din lösning)...".
Yngve skrev :Andno skrev :Yngve skrev :Hej och välkommen till Pluggakuten Andno!
Metoden går ut på att pröva alla tal som är mindre än det aktuella talet.
Den tid det tar är då linjärt beroende av antalet tal som är mindre än det aktuella talet, inte hur många siffror talet innehåller, inte heller hur många primtal det finns som är lägre än talet själv.
Exempel:
Talet 9 har 1 siffra och 8 (positiva hel)-tal som är mindre än talet.
Talet 99 har 2 siffror (dubbelt så många), men hela 98 (positiva hel)-tal som är mindre än.talet.
98 är mer än dubbelt så stort som 8, så.det skulle ta mer än dubbelt så lång tid att testa om 99 är ett primtal som att testa om 9 är det.
Hej, tack!
Ja, det är helt sant, tänkte nog inte riktigt till där. Dock försåt jag ändå inte riktigt hur jag ska kunna besvara frågan exakt när jag inte vet vad talen är exakt. Är det meningen att man bara ska ta två tal, ett med 10 siffror och ett med 20 siffror? Eller ska man ge ett mer generellt svar utan att göra ett antagande om vad de två talen är exakt?
Du ska inte svara exakt. Det står att du ska göra en uppskattning av hur lång tid det kan ta.
Välj ett tal med 40 siffror, till exempel 1*10^39 och ett tal.med 20 siffror, till exempel 1*10^19.
Hur många gånger större är det 40-siffriga talet än det 20-siffriga talet?
Denna faktor kan du sen använda för att beräkna uppskattad datortid.
Du kan även experimentera med intervall.
Ta då ett så stort 40-siffrigt tal.som möjligt och jämför med ett så litet 20-siffrigt tal som möjligt.
Gör sedan tvärtom, ta ett så litet 40-siffrigt tal som möjligt och jämför med ett så stort 20-siffrigt tal som möjligt.
Ditt svar kan sedan använda dessa kvoter som bas för en max/min-uppskattning
I uppgiften så stod det att "En metod att faktorisera och hitta primtalsfaktorerna är att prova att dela med olika tal som är mindre än det ursprungliga talet" men det stod också att jag kan använda en annan metod.
Så det jag gjorde var att ta två tal, ett med 20 siffror och ett med 40 siffror, och uppskattade hur många primtal som är mindre än respektive tal enligt Lirim.Ks metod. Det tog 1 minut att dela ett tal med 20 siffror på var och en av de primtalen, som är mindre än det ursprungliga talet, innan man hittade faktorerna. Då kan man även uppskatta hur lång tid det tar att göra samma sak för ett tal på 40 siffror då man har uppskattat antalet primtal under det. Tidsskillnaden var ju enorm, jag provade inte för flera tal på 20 respektive 40 siffror utan tog ett vardera och tror det egentligen räcker.
Tack för din hjälp!
