Är det ett primtal: Skillnad mellan sidversioner

Från Wikiskola
Hoppa till navigering Hoppa till sök
 
(8 mellanliggande sidversioner av samma användare visas inte)
Rad 1: Rad 1:
=== Dynamic Programming ===
[[Kategori:Python]] [[Kategori:Ma1c]]  [[Kategori:Aritmetik]]  [[Kategori:Årskurs 7-9]]
{{python|[[Python|Python-hjälp]]}}
{{malruta| '''Kom igång med programmering i matematiken.'''


A function evaluating if input integer is prime (in Python script):
Målet är att du ska köra enkla färdiga program för att utföra matematiska beräkningar.
Du bör testa att modifiera algoritmen så att dina beräkningar blir mer effektiva.


<pre>
Målet är inte att du ska lära dig programmering på matematiklektionen men det är oundvikligt att du ändå lär dig lite Python-kod.  
def prime(input):
}}
    for n in range(2, input):
        if input%n == 0:
            return False
    return True
 
tal = int(input("ange ett tal"))
if (prime(tal) == True):
  print(tal, "är ett primtal")
else:
print(tal, "är inte ett primtal")
</pre>
 
Essentially, this evaluates whether integer x can be divisible by any number less than it (n = [2, 3, 4, ... , x-2, x-1]). However, there are two redundancies in this method:
 
1. If input is not divisible by 2, it will not be divisible to any other even number (4, 6, 8, ...).


2. It is not needed to evaluate integers above the square root of the input number. To elaborate, here is an example:
== Uppgift ==


Evaluate if 127 is prime:
Man kan antingen använda programmet som intro till en lektion om primtal i Ma1c. Det tar inte många minuter men vänjer eleverna vid att köra program.
127 divisible by 2? No.
127 divisible by 3? No.
127 divisible by 5? No.
127 divisible by 7? No.
127 divisible by 9? No.
127 divisible by 11? No.
Therefore 127 is prime.


We do not need to evaluate if 127 is divisible by 13, because 127<sup>1/2</sup> is around 11.27, which is smaller than 13. If 127 was divisible by 13, then 127/13 would be less than 13 itself and therefore must give an integer already tested. As another example, 143 will be checked if it is prime. Here it will be shown that 13 is not needed to be evaluated once again (143<sup>1/2</sup> ≈ 11.96).
Eller så arbetar man med att undersöka och förbättra algoritmen vilket tar betydligt mer tid.


143 divisible by 3? No.
== Koden ==
143 divisible by 5? No.
143 divisible by 7? No.
143 divisible by 9? No.
143 divisible by 11? Yes → 143/11 = 13
(143 divisible by 13 not evaluated)
Therefore, 143 is not prime


Hence, our original prime function can be improved using these two suggestions, and now runs at a greater speed! For example, when evaluating if 10001 is prime, the function went through 10000 different numbers. But with these improvements, it only has to go through 50!
Vi använder en funktion som testar om tal är ett primtal. Resten av koden är för inmatning och utmatning av resultatet.


<pre>
<pre>
from math import ceil
def prime(input):
def prime(input):
     for n in [2] + range(3, int(ceil(input**0.5)), 2):
     for n in range(2, input):
         if input%n == 0:
         if input % n == 0:
             return False
             return False
     return True
     return True
 
tal = int(input("Ange ett tal "))
if (prime(tal) == True):
  print(tal, " är ett primtal")
else:
  print(tal, " är inte ett primtal")
</pre>
</pre>


Now, this only tests odd numbers (≥3) and ≤ the square root of the input (hence the ceil function, which can be replaced with a simple "+1").
För att förbättra algoritmen, se diskussionssidan.
 
So here is the lesson to learn from this: the gun is only as accurate as you are.

Nuvarande version från 5 april 2018 kl. 09.46

Programmeringsuppgift

Python-hjälp

Mål för undervisningen Kom igång med programmering i matematiken.

Målet är att du ska köra enkla färdiga program för att utföra matematiska beräkningar. Du bör testa att modifiera algoritmen så att dina beräkningar blir mer effektiva.

Målet är inte att du ska lära dig programmering på matematiklektionen men det är oundvikligt att du ändå lär dig lite Python-kod.


Uppgift

Man kan antingen använda programmet som intro till en lektion om primtal i Ma1c. Det tar inte många minuter men vänjer eleverna vid att köra program.

Eller så arbetar man med att undersöka och förbättra algoritmen vilket tar betydligt mer tid.

Koden

Vi använder en funktion som testar om tal är ett primtal. Resten av koden är för inmatning och utmatning av resultatet.

def prime(input):
    for n in range(2, input):
        if input % n == 0:
            return False
    return True
   
tal = int(input("Ange ett tal "))
if (prime(tal) == True):
  print(tal, " är ett primtal")
else:
  print(tal, " är inte ett primtal")

För att förbättra algoritmen, se diskussionssidan.