Diskussion:Är det ett primtal - Versionshistorik

Hakan den 21 mars 2018 kl. 23.25

2018-03-21T23:25:15Z

@@ Rad 1: / Rad 1: @@
 A function evaluating if input integer is prime (in Python script):
@@ Rad 24: / Rad 23: @@
 divisible by 11? No.
   Therefore 127 is prime.
 Från [https://en.wikibooks.org/wiki/Python_and_Math WikiBooks]

Hakan den 21 mars 2018 kl. 23.21

2018-03-21T23:21:57Z

← Äldre version		Versionen från 21 mars 2018 kl. 23.21
Rad 1:		Rad 1:
	~~[[Kategori:Python]]~~
	~~{{python\|[[Python\|Python-hjälp]]}}~~
	~~{{malruta\| '''Kom igång med programmering i matematiken.'''~~

	~~Målet är att du ska köra ditt första 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.~~
	}}

	A function evaluating if input integer is prime (in Python script):		A function evaluating if input integer is prime (in Python script):

Hakan: /* Dynamic Programming */

2018-03-21T22:11:57Z

Dynamic Programming

@@ Rad 1: / Rad 1: @@
-=== Dynamic Programming ===
+[[Kategori:Python]]
-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 ditt första program för att utföra matematiska beräkningar.
 A function evaluating if input integer is prime (in Python script):
@@ Rad 28: / Rad 34: @@
   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).
+Från [https://en.wikibooks.org/wiki/Python_and_Math WikiBooks]

Hakan: Skapade sidan med '=== Dynamic Programming === 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 for...'

2018-03-21T22:07:03Z

Skapade sidan med '=== Dynamic Programming === 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 for...'

Ny sida

=== Dynamic Programming ===

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.

A function evaluating if input integer is prime (in Python script):

<pre>
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:

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:

Evaluate if 127 is prime:
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>
from math import ceil
def prime(input):
for n in [2] + range(3, int(ceil(input**0.5)), 2):
if input%n == 0:
return False
return True
</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").

So here is the lesson to learn from this: the gun is only as accurate as you are.