Är det ett primtal: Skillnad mellan sidversioner

Från Wikiskola
Hoppa till navigering Hoppa till sök
VisuellWikitext
 
(10 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.'''


The main bulk of what this Wiki-book will discuss will be on how to improve your programs so that they run faster and more efficiently. A more formal introduction to this will be made later, but below is an example of what I mean.
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.


A function evaluating if input integer is prime (in Python script):
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.
}}


<pre>
== Uppgift ==
def prime(input):
    for n in range(2, input):
        if input%n == 0:
            return False
    return True
</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:
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.


1. If input is not divisible by 2, it will not be divisible to any other even number (4, 6, 8, ...).
Eller så arbetar man med att undersöka och förbättra algoritmen vilket tar betydligt mer tid.


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


Evaluate if 127 is prime:
Vi använder en funktion som testar om tal är ett primtal. Resten av koden är för inmatning och utmatning av resultatet.
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).
 
143 divisible by 3? No.
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!


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

Hämtad från ”https://wikiskola.se/index.php?title=Är_det_ett_primtal&oldid=46299”