Primtal

Hej och välkommen till Pluggakuten!

Till att börja med: Vet du hur man kontrollerar om ett tal är ett primtal? 

Talet ska bara gå att delas med sig själv och ett...men hur kodar jag det?

Tänker att jag måste använda en if sats

Jo, rimligtvis blir det ett villkor någonstans. Det lär också bli en loop. 

Har du hört talas om pseudokod? Det är ofta en bra start innan man börjar skriva kod. Alltså ett "program" skrivet på svenska som beskriver vad som skall göras.

Hur skulle du själv kontrollera om 43 är ett primtal? Beskriv det för dig själv så kommer du nog att upptäcka att du behöver en loop och även ett villkor. 

Därefter kan du översätta det till python och vi hjälper gärna till.

Jag skulle börja så här:

be om ett nummer
om är_primtal(nummer) är sant:
    skriv ut: 'nummer' är ett primtal
annars:
    skriv ut: 'nummer' är inte ett primtal

Sedan skulle jag på samma sätt fundera på hur funktionen är_primtal(nummer) skall fungera.

När jag har en idé om hur den skall fungera, översätter jag den till python.

Jag vill ge ett förslag på kod du kan testa mot sedan när du är klar:

def prime_checker(n):
    if n == 2:
        return 1

    for i in range(2, n):
        if n % i == 0:
            return 0
	
    return 1

Denna kod returnerar 1 om talet är ett primtal och 0 om det är ett sammansatt tal. 

Ett tips för din kod att du borde fundera på operatorn %. Med % kollar du på resten mellan två tal. T.ex. 10 % 3 = 1, eftersom 10 ger rest 1 vid division med 3. Vilken rest får man mellan två tal,  $n$ och $k$, om $n$ är delbart med $k$? När du har svaret på den frågan kan du formulera ditt villkor! :)

Hej igen!

Tack för svar, bra tips. Men tyvärr förstår jag inte hur jag ska gå till väga. Någon snäll själ som vill dela med sig och förklara HUR man gör?!

Siakakan skrev:

Hej igen!

Tack för svar, bra tips. Men tyvärr förstår jag inte hur jag ska gå till väga. Någon snäll själ som vill dela med sig och förklara HUR man gör?!

Jag skulle göra så här:

1. Fråga efter ett tal.
2. Kontrollera följande:
   1. Om talet är <2 så är det inte ett primtal.
   2. Om talet är =2 så är det ett primtal.
   3. Om talet är jämnt så är det inte ett primtal.
3. Sedan får vi prova att dividera talet med alla udda tal, upp till kvadratroten av talet.
   1.  Så snart vi hittar ett tal som är jämnt delbart, vet vi att det inte är ett primtal.
4. Hittar vi inget sådant tal är talet ett primtal.

Försök skriva kod som motsvarar ovanstående.

Saker att fundera på:

• Varför upp till kvadratroten av talet?
• Varför bara testa att dividera med udda tal?

Jag bifogar ett kodexempel, men se till att förstå det. Fråga annars! 

def är_primtal(tal):
    if tal <= 1:
        return False
    if tal == 2:  # 2 är ett primtal
        return True
    if tal % 2 == 0:  # Jämna tal större än 2 är inte primtal
        return False
    # Kolla bara udda delare från 3 upp till kvadratroten av talet
    for i in range(3, int(tal ** 0.5) + 1, 2):
        if tal % i == 0:
            return False
    return True

# Testa programmet
nummer = int(input("Ange ett tal: "))
if är_primtal(nummer):
    print(f"{nummer} är ett primtal.")
else:
    print(f"{nummer} är inte ett primtal.")

Hej!

Vad menar du här:

Sedan får vi prova att dividera talet med alla udda tal, upp till kvadratroten av talet.

Så snart vi hittar ett tal som är jämnt delbart, vet vi att det inte är ett primtal

Förstår inte varför jag ska göra så...

Siakakan skrev:

Hej!

Vad menar du här:

Sedan får vi prova att dividera talet med alla udda tal, upp till kvadratroten av talet.

Så snart vi hittar ett tal som är jämnt delbart, vet vi att det inte är ett primtal

Förstår inte varför jag ska göra så...

Hej!

Vilken del förstår du inte? Varför man skall prova att dividera med alla udda tal, eller varför man kan sluta prova efter kvadratroten av talet?

Det var min fråga i svar #2: Vet du hur man kontrollerar om ett tal är ett primtal? 

Hej igen!

Jag vet hur man kollar om ett tal är ett primtal. Man faktoriserar talet, hittar man enbart faktorn 1 och talet själv är det ett primtal. Men förstår inte det där med kvadratroten...

Siakakan skrev:

Hej igen!

Jag vet hur man kollar om ett tal är ett primtal. Man faktoriserar talet, hittar man enbart faktorn 1 och talet själv är det ett primtal. Men förstår inte det där med kvadratroten...

Finemang!

Vi tar 43 som exempel, där $\sqrt{43}\approx 6,56$:

Delbart med ...

• 3? Nej.
• 5? Nej.
• 7? Nej.

Behövde vi ens testa faktorn 7?

Nix! För om sju varit en faktor så hade ju $43=7x$. Men vi har ju testat för alla x < 7 redan, så vi vet att x inte kan vara några av dem. Det skulle kunna vara 7*7, men det är >43.

Därför behöver vi inte testa med alla faktorer upp till talet, utan kan reducera mängen till roten av talet. För stora tal gör det stor skillnad.

OK?

Ok, nu förstår jag! Tack för ditt tålamod.

Siakakan skrev:

Ok, nu förstår jag! Tack för ditt tålamod.

NP! Bara skoj med programmeringsfrågor. Ser fram emot nästa.