Nächste höhere Primzahl und Palindromzahl

Gibt es einen Vorschlag für die Lösung der nächsten höheren Primzahl und Palindrome Zahl aus einer gegebenen int.

Hier ist das Snippet, das ich versuche, aber es ist eine Art von langsam, bitte vorschlagen, wenn Sie irgendeinen guten Algorithmus haben, den ich testen kann.

#!/usr/bin/python def next_higher(n): while True: s = str(n) if not any([n % i == 0 \ for i in range(2, int(n**0.5))]) and s == s[::-1]: return n n = n + 1 print next_higher(2004) print next_higher(20) 

Ausgabe:

 10201 101 

Aktualisierte Code-Tests für Palindrome vor Prime. Viel schneller als mein früherer Code. Ich verwende den Vorschlag von user2357112.

  #!/usr/bin/python def next_higher(n): while True: s = str(n) if s == s[::-1]: if not any([n % i == 0 \ for i in range(2, int(n**0.5))]): return n n = n + 1 print next_higher(2004111) print next_higher(2004) print next_higher(2004) print next_higher(20) 

  • Python-Datenstruktur für effiziente Add-, Remove- und Random.choice
  • Wie man einen Median-Haufen implementiert
  • Lösche den Knoten im Binärsuchbaum python
  • Konvertieren einer Liste von Tupeln in ein Dict in Python
  • Eine Datenstruktur für 1: 1-Mappings in Python?
  • Entfernen von Elementen aus einer Liste mit bestimmten Zeichen
  • 4 Solutions collect form web for “Nächste höhere Primzahl und Palindromzahl”

    Es gibt ein paar Optimierungen, die du tun kannst:

    • Wie User2357 .. in den Kommentaren vorgeschlagen, Test Palindromeness zuerst, und dann überprüfen, ob die Nummer ist prim, da Prime Check ist teurer.
    • Sie müssen nicht einmal die Teilteilbarkeit überprüfen, sobald Sie überprüfen, dass die Nummer durch 2 teilbar ist. So können Sie sie auf [2] + range(3, int(n**0.5) + 1, 2) ändern, um nur zu überprüfen Ungerade Zahlen nach 2. (Auch müssen Sie sqrt + 1 wie ich in den Kommentaren erwähnt zu tun)
    • Du solltest () anstelle von [] . [] Generiert die gesamte Liste der Faktoren zuerst und nur dann prüft auf any . Wenn Sie () , erzeugt es einen Generator, also stoppt er, sobald ein True Wert gefunden wird, ohne die gesamte Liste zu berechnen.
    • Sie sollten auch xrange statt range aus dem gleichen Grund ( xrange gibt einen Generator, range gibt eine Liste)
    • Sie können den Sieb des Eratosthenes- Algorithmus verwenden, um die Zeit für die Prime Number Check zu reduzieren.
    • Sie können auch sehen, ob der Palindrome-Check schneller gemacht werden kann. Sie können tatsächlich eine ganze Anzahl von Zahlen überspringen, anstatt nur noch einmal + 1 tun.

    Hier ist eine Version mit den meisten dieser Optimierungen außer den letzten beiden:

     def next_higher(n): if n % 2 == 0: n = n - 1 while True: n = n + 2 s = str(n) if s == s[::-1]: if not any((n % i == 0 for i in xrange(3, int(n**0.5) + 1, 2))): return n 

    Das sollte ziemlich schnell für deine Bedürfnisse sein, glaube ich. Aber du kannst die letzten 2 Optimierungen machen, um es noch viel schneller zu machen, wenn du willst.

    Anders als das, was bereits vorgeschlagen wurde,

    Was ich vorschlage, ist, dass du zuerst die erste Palindrome-Nummer bekommst, die gerade höher ist als die gegebene ganze Zahl.

    Sie können dies tun, indem Sie versuchen, die Ziffern nach außen zu passen.

    Auch solltest du nur nach Nummern mit ungeraden Zifferntasten suchen, denn wenn eine Zahl noch eine Anzahl von Ziffern hat und es ein Palindrom ist, dann wird es immer um 11 teilbar und kann nicht prima sein.

    Sobald Sie die erste Palindrome-Nummer, die ungerade Anzahl von Ziffern hat und das ist nur höher als die aktuelle Nummer, testen Sie es für die Primalität und finden Sie die nächste Palindrome-Nummer höher als diese.

    Sie können dies tun, indem Sie die Mittelziffer erhöhen.

    Halten Sie das, bis es auf Null geht. Starten Sie in diesem Fall die beiden benachbarten Ziffern.

    Weiter, bis du eine Primzahl erreichst.

    Ich habe versucht, die Palindrome-Prüfung zu optimieren, um seltsame Palindrome zu finden. Da die erste Ziffer ungerade Nummer sein sollte, konzentrierte ich mich auf diesen Teil. Hier ist der Code unten mit den Annahmen seine mehr als 1 Ziffer.

     def next_odd_palindrome(n): """to check the next odd palindrome number""" if n%2==0: n=n-1 while True: n=n+2 s = str(n) if int(s[0])%2==0: n = int(str(int(s[0])+1)+ s[1:]) s = str(n) if s==s[::-1]: return n 

    Lassen Sie mich wissen, wenn etwas falsch ist

    Nur für den Spaß daran habe ich alle Optimierungen von Hari Shankar und Abhishek Bansal implementiert.

    Es findet zuerst die höhere ungerade Länge Palindrome, dann inkrementieren die Palindrome in einer Weise, die seine Palindromity hält. Dann prüft jede Zahl mit Primzahlen, die von der Sieve-Methode am Anfang berechnet wurden.

    Dies kann bis zu n=10^14 (kann höher sein, wenn man die CACHE-Größe erhöht) unter 1 Sekunde in meinem Computer = D

     primes = [] CACHE = int(10**7) # Cache size for Sieve # Custom class for immediate printing of output import sys class Unbuf: def __init__(self,stream): self.stream = stream def write(self,data): self.stream.write(data) self.stream.flush() sys.stdout = Unbuf(sys.stdout) def sieve(): global primes is_prime = [False,False]+([True]*(CACHE-1)) for i in xrange(2,int(CACHE**0.5)): if is_prime[i]: is_prime[i*i::i] = [False]*((CACHE-i*i+i)/i) primes = [num for num, bool_prime in enumerate(is_prime) if bool_prime] def is_prime(n): """Checks whether n is prime""" global primes if n<2: return False if n==2: return True for prime in primes: if prime>n**0.5+1: return True if n%prime==0: return False # For the case that the number is bigger than the square of our largest prime for num in xrange(primes[-1]+2,n**0.5+1,2): if n%num==0: return False return True def next_higher_odd_length_palindrome(n): n = str(n) if len(n)%2==0: # Even length, take the smallest odd length (10(00)*1) n = '1'+('0'*(len(n)-1))+'1' else: middle_idx = len(n)/2 left = int(n[:middle_idx+1]) left_cmp = n[middle_idx::-1] right_cmp = n[middle_idx:] # If mirroring left part to right part # makes the number smaller or equal, then if right_cmp>=left_cmp: # Increase the left half number left = left+1 # Mirror left part to the right part n = str(left)+str(left)[-2::-1] return n def next_higher(n): if n<=1: return 2 # Ensure the number is a palindrome of odd length n = next_higher_odd_length_palindrome(n) while True: if is_prime(int(n)): return int(n) n = next_higher_odd_length_palindrome(n) if int(n[0])%2==0: new_lead = str(int(n[0])+1) n = new_lead+n[1:-1]+new_lead import time print 'Sieving...', start_time = time.time() sieve() print 'Done in %.3fs' % (time.time() - start_time) print next_higher(2004111) print next_higher(2004) print next_higher(20) while True: n = int(raw_input('Enter n: ')) start_time = time.time() result = next_higher(n) print 'Next higher prime palindrome: %d (calculated in %.3fs)' % (result, time.time() - start_time) 

    Was in meinem Computer gibt diese Ausgabe:

     Sieben ... Geschehen in 1.444s
     3007003
     10301
     101
     Geben Sie n: 1999999999 ein
     Nächstes höheres prime palindrome: 10000500001 (berechnet in 0,004s)
     Geben Sie n: 1999999999999 ein
     Nächstes höheres prime palindrome: 3000002000003 (berechnet in 0,051s)
     Geben Sie n: 1000000000000 ein
     Nächstes höheres prime palindrome: 1000008000001 (berechnet in 0,030s)
     Geben Sie n:
    
    Python ist die beste Programmiersprache der Welt.