#!/usr/bin/env python
# coding: utf-8

# # Mit Python Primzahlen finden

# ## Ein nicht sehr effektiver Algorithmus

# Im nachfolgenden Teil werden wir versuchen, einen Primzahlfilter zu schreiben, der uns die Primzahlen aus einem gegebenen Intervall zurückgibt.

# ### Was ist eine Primzahl?
# Eine Primzahl ist eine Zahl die nur durch sich selbst und durch eins Teilbar ist. 1 (Eins) ist keine Primzahl. 2 (Zwei) ist die erste Primzahl und die einzig gerade.
# Mit diesem Wissen koennen wir nun anfangen

# ### Teilbarkeit einer Zahl bestimmen
# Um zu überprüfen, ob eine gegebende Zahl durch eine andere Zahl teilbar ist, können wir den Modulo-Operator (%) nutzen. Dieser gibt den Rest bei einer ganzzahligen Teilung wieder. Ist _a_ also durch _b_ teilbar, dann ist _a_ % _b_ 0.
# Dies können wir wie folgt schreiben:

# In[1]:


12 % 4 == 0


# ### Ist eine Zahl eine Primzahl?
# Wir schreiben eine Funktion, die:
# * eine natuerliche Zahl a als Argument bekommt
# * entweder _True_ oder _False_ zurueckgibt, je nachdem ob es sich um eine Primzahl handelt

# In[2]:


def is_prime(a):
    if a == 1:
        return False
    
    for i in range(2, a):
        if a % i == 0:
            return False
        
    return True


# In[3]:


is_prime(2)


# Diese Funktion funktioniert und entscheided wahrheitsgemäß, ob es sich bei dem Argument um eine Primzahl handelt oder nicht. Nun werden wir eine Liste an Primzahlen ausgeben. Hier zwei Ansaetze:

# #### Mit einer Schleife:

# In[4]:


def primelist(upper_boundry):
    primes = []
    for i in range(2, upper_boundry):
        if is_prime(i):
            primes.append(i)
    return primes


# In[5]:


primelist(50)


# #### Der funktionale Ansatz:

# In[6]:


def primelist_filter(upper_boundry):
    return list(filter(is_prime, range(1, upper_boundry)))


# In[7]:


primelist_filter(50)


# Nun haben wir einen "Primzahlgenerator", der uns eine List von Primzahlen ausgibt. Allerdings ist dieser Ansatz ziemlich ineffizient. Wie koennte man den Generator nun verbessern? 

# ## Ein besserer Algorithmus:

# Jede natuerliche Zahl, die keine Primzahl ist, laesst sich als produkt aus Primzahlen darstellen. Die Zahl 10 laesst sich in die Primzahlfaktoren  5 und 2 zerlegen.
# 
# **Primzahlfaktoren anderer Zahlen:**
# 
# `` 
# 10  ->  [2, 5]
# 12  ->  [2, 2, 3]
# 14  ->  [2, 7]
# 27  ->  [3, 9]
# ``

# **Also:**
# Wenn eine Zahl keine Primzahl ist, laesst sie sich also als Produkt von Primzahlen darstellen. Somit muessen wir bei der Probe von Primzahlen nur pruefen, ob unser Kandidat durch irgendeine Primzahl teilbar ist.

# In[8]:


def faster_primecheck(candidate, found_primes):
    for i in found_primes:
        if candidate % i == 0:
            return found_primes
    found_primes.append(candidate)
    return found_primes


# In[9]:


faster_primecheck(3,[2])


# Die Funktion gibt uns eine Liste zurueck, die eventuell ein neues Element enthaelt. Wenn der Kandidat hinzugefuegt wurde dann handelt es sich entweder um eine Primzahl, oder ``found_primes`` ist zu kurz. Nun schreiben wir einen Generator basierend auf diesen Erkenntnissen:

# In[14]:


def faster_primelist(upper_limit):
    primes = []
    for i in range(2, upper_limit):
        primes = faster_primecheck(i, primes)
    return primes


# In[15]:


faster_primelist(50)