Python - Prime Kontrolle und erhöhen

Question

Mein Ziel des folgenden Code ist

1. überprüfen, ob eingegebene Zahl eine Primzahl
2. wenn nicht die nächste größte Primzahl drucken

---

def primetest (num):  
    for c in range (2, num):  
    if num % c == 0: 
     repeattest (num)   #not prime? increment number 
    else : 
     print (num,"is a prime number") 
     break   

def repeattest (num):  # check prime if not increment number by 1   
for z in range (2, num): 
    num = num+1 
    primetest (num)  
    if num % z == 0: 
     num = num+1 
    else: 
     print ("Next Prime:", num+1) 
     break 

num = int (input ("enter a number:"))  # main code: 
for y in range (2, num): 
    if num % y == 0: 
     repeattest (num) 
    else: 
     print (num,"is a prime number") 
     break 

Ich denke, die Logik ist in Ordnung, aber nicht sicher, warum ich keine Ausgabe bekomme.

Answer 1

Die Zeitkonstante Ihres Codes ist O (N), wenn er eine Zahl findet, die prim ist oder nicht. Beim Teilen von 2 nach len (num) -1 wird nicht angezeigt. Es ist genug, um von 2 zu sqrt der gegebenen Zahl zu wiederholen. Daher reduziert sich die Zeitkomplexität auf O (n) zu O (log (n)).

import math 
num = int (input ("enter a number:")) 

def primeTest(num): 
    isPrime = 0 
    for i in range(2,int(math.sqrt(num)+1)): 
     if num%i == 0: 
      isPrime = isPrime + 1 
      break 
    if isPrime == 0: 
     print(num, "is a prime number") 
    else: 
     num = num + 1 
     repeatTest(num) 

def repeatTest (num): 
    isPrime = 0 
    for i in range(2,int(math.sqrt(num))): 
     if num%i == 0: 
      isPrime = isPrime + 1 
      break 
    if isPrime == 0: 
     print("Next Prime: ", num) 
    else: 
     num = num + 1 
     repeatTest(num) 

primeTest(num) 

Answer 2

Die Logik, die Sie verwenden, um zu finden, ob eine Zahl, wenn Prime scheint falsch.

Mit einer Ganzzahl wie 9 Drucke "9 ist eine Primzahl".

Und auch Sie suchen nach nächsten Primzahlen von 2 bis Num. Num die Eingabe, Sie können eine Zahl größer als das bekommen. Es verlässt die Schleife, ohne hineinzukommen, und druckt daher nichts, wenn Sie nach der nächsten Primzahl suchen.

Sie müssen die Logik ändern.

schreiben Sie eine separate Funktion für die Überprüfung von Prime und beenden Sie die Schleife, wenn Sie die nächste Primzahl finden, anstatt bei num zu stoppen.