Prvočísla

Empirická analýza časové složitosti nalezení prvočísel menších než zadaný limit

import sys
import time
import matplotlib.pyplot as plt

Najdi prvočísla menší než m a vrať je v poli. Postup z definice

def prvocisla_jednoduse(m):
  primes=[]
  for n in range(2,m): # cyklus 2..m-1
    p=2 # začátek testu
    while p<n:
      if n % p == 0:
        break
      p+=1
    if p==n: # n je prvočíslo
      primes+=[p]
  return primes    

Najdi prvočísla menší než m a vrať je v poli. Testujeme jen do odmocniny z p

def prvocisla_odmocnina(m):
  primes=[]
  for n in range(2,m): # cyklus 2..m-1
    p=2 # začátek testu
    while p*p<n:
      if n % p == 0:
        break
      p+=1
    if p*p > n: # n je prvočíslo
      primes+=[n]
  return primes    

Najdi prvočísla menší než m a vrať je v poli. Algoritmus Eratosthenova síta

def prvocisla_eratosthenes(m):
  primes=[]
  p=[True]*m #  p[i] = je 'i' prvočíslo?
 
  for i in range(2,m):
    if p[i]: # je to prvočíslo
      primes+=[i]
      j=2*i # označ j=2i,3i,... < m
      while j<m:
        p[j]=False
        j+=i
  return primes    

Najdi prvočísla menší než m a vrať je v poli. Vylepšený algoritmus Eratosthenova síta

def prvocisla_eratosthenes2(m):
  primes=[2]
  p=[True]*m #  p[i] = je 'i' prvočíslo?
 
  i=3
  while i*i <= m:
    if p[i]: # je to prvočíslo
      primes+=[i]
      j=2*i # označ j=2i,3i,... < n
      while j<m:
        p[j]=False
        j=j+i
    i+=2
  while i<m: # označ zbytek
    if p[i]: # je to prvočíslo
      primes+=[i]
    i+=2  
  return primes    

Otestujeme implementace hledání prvočísel pro malé n

def test_small():
  n=100
  for f in implementations:
     print(f.__name__," returned ", f(n))
 
def test_big():
  """ Otestujeme implementace hledání prvočísel pro větší n a porovnáme automaticky"""
  n=10000 
  primes=implementations[0](n)
  for f in implementations[1:]:
    p=f(n)
    if p==primes:
        print(f.__name__," passed")
    else:
        print(f.__name__," failed.")
        return False
  print("All implementations passed.")
  return True
 
def time_and_plot():
  """ Změříme čas trvání všech implementací pro různá 'n' """
  ns=[100,300,1000,3000,10000,30000,100000]
  plt.figure(1)      
  for f in implementations:
    ts=[]
    print("Implementation : ",f.__name__)
    for n in ns:
      t0=time.clock() # start timing
      f(n)            # execute f and discard results
      t=time.clock()-t0
      print("  n=%6d CPU time=%6.3fs" % (n,t))
      ts+=[t]
    # plt.plot(ns,ts,marker='o',label=f.__name__)
    plt.loglog(ns,ts,marker='o',label=f.__name__)  
  plt.xlabel('m')
  plt.ylabel('time [s]')
  plt.legend(loc='upper left')
  plt.axis([0.,max(ns).,0.,0.5])
  #plt.savefig("prvocisla_cas.pdf")
  plt.savefig("prvocisla_cas_log.pdf")
  plt.show()
 
if __name__=="__main__":
  time_and_plot()