Seite 1 von 1
Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 16:22
von hansjürgen
Ich versuche mich gerade an folgender Aufgabe:
https://www.codewars.com/kata/gap-in-pr ... ain/python
Ich habe auch folgendes Programm dazu geschrieben
Code: Alles auswählen
import random
def miller_rabin(m, k=7):
s=1
t = (m-1)/2
while t%2 == 0:
t /= 2
s += 1
t = int(t)
for r in range(0,k):
rand_num = random.randint(1,m-1)
y = pow(rand_num, t, m)
prime = False
if (y == 1):
prime = True
for i in range(0,s):
if (y == m-1):
prime = True
break
else:
y = (y*y)%m
if not prime:
return False
return True
def prim_generator(untere_Schranke,obere_Schranke):
return [i for i in range(untere_Schranke,obere_Schranke+1) if miller_rabin(i)]
def gap(g,m,n):
a = prim_generator(m,n)
for i in range(0,len(a)-1):
if a[i+1]-a[i]==g:
return [a[i],a[i+1]]
return None
Dieses Programm funktioniert zwar fehlerlos,jedoch ist es zu langsam und somit kriege Ich die Aufgabe nicht gelöst.
Meine Frage lautet nun wie kann Ich das Programm optimieren ?
Re: Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 16:38
von ThomasL
Meinst du es ist notwendig dafür den Miller-Rabin-Test zu implementieren?
Ich kann in der Aufgabenstellung dazu nichts lesen.
Den Test auf Prim oder nicht kann man wesentlich schneller machen. (ist auch hier im Forum schon gepostet worden)
Re: Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 17:10
von __blackjack__
@hansjürgen: Du musst ja nur die ersten beiden Zahlen ausgeben auf die das Kriterium zutrifft, berechnest aber erst einmal *alle* aus dem Bereich. Das ist unter Umständen viel zu viel Arbeit.
Re: Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 18:49
von hansjürgen
ThomasL hat geschrieben: Donnerstag 2. August 2018, 16:38
Meinst du es ist notwendig dafür den Miller-Rabin-Test zu implementieren?
Ich kann in der Aufgabenstellung dazu nichts lesen.
Den Test auf Prim oder nicht kann man wesentlich schneller machen. (ist auch hier im Forum schon gepostet worden)
Als Ich gesehen habe, dass das Programm zu langsam ist habe Ich angefangen den schnellsten Primzahltest-Algorithmus zu implementieren,da Ich darin den Grund gesehen habe warum mein Programm zu langsam ist.
Mir ist kein schnellerer Algorithmus als der Miller-Rabin Test bekannt
Re: Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 19:06
von ThomasL
Code: Alles auswählen
from math import ceil, sqrt
def is_prime(number):
if number % 2 == 0 and number != 2:
return False
else:
return all(number % factor != 0
for factor in range(3, ceil(sqrt(number)) + 1, 2))
def prime_generator(low, high):
return [i for i in range(low, high+1) if is_prime(i)]
def gap(g, m, n):
primes = prime_generator(m, n)
for i in range(0, len(primes)-1):
if primes[i+1] - primes[i] == g:
return [primes[i], primes[i+1]]
return None
Dieser Code ist ca. 8x schneller als der mit dem Miller-Rabin-Test.
Die Sample-Tests laufen auch durch:
Code: Alles auswählen
Time: 534ms Passed: 5 Failed: 0
Test Results:
Gap
Basic tests (5 of 5 Assertions)
You have passed all of the tests! :)
Aber der Main-Attempt steigt auch hier nach 12000ms aus.
Da werden wohl ziemlich grosse Ranges und Gaps abgefragt.
Re: Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 19:07
von hansjürgen
Dank dem Kommentar von _blackjack_ konnte Ich das Programm verbessern, sodass es schenll genug läuft um den Test zu bestehen.
Code: Alles auswählen
import random
def miller_rabin(m, k=7):
if m%2 == 0:
return False
s=1
t = (m-1)/2
while t%2 == 0:
t /= 2
s += 1
t = int(t)
for r in range(0,k):
rand_num = random.randint(1,m-1)
y = pow(rand_num, t, m)
prime = False
if (y == 1):
prime = True
for i in range(0,s):
if (y == m-1):
prime = True
break
else:
y = (y*y)%m
if not prime:
return False
return True
def gap(g,m,n):
p=m
a = []
while(True):
if p > n: return None
if miller_rabin(p): a.append(p)
p+=1
if len(a) > 1:
if a[-1]-a[-2] == g:
return [a[-2],a[-1]]
Vielen Dank für die Hilfe
Re: Codewars Aufgabe Gap in Primes
Verfasst: Donnerstag 2. August 2018, 19:37
von ThomasL
Jo, die neue gap() ist mal eben ca. 670x schneller (bei mir und mit gap(10, 3000, 4000))
Bzgl. schnelle Primtests; hatte den hier gerade noch gefunden
https://en.wikipedia.org/wiki/AKS_primality_test
Ist aber mit der neuen gap() und obigen Werten genau so schnell wie der Miller-Rabin.
Es lag also nicht am Primzahlentest sondern an der gap() Funktion.