Codewars Aufgabe Gap in Primes

[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 ?

[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)

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

[hansjürgen]

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

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

[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

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