Berechnen Sie alle möglichen Faktoren einer Primzahl

Ging durch ein Python-Tutorial und kam auf ein Beispiel, um zu überprüfen, ob eine Zahl prima ist oder nicht. Ich änderte ein paar Sachen, so dass das Ergebnis eine Liste aller möglichen Faktoren der Zahl anzeigen würde, wenn die Zahl nicht eine Primzahl ist, aber der Code funktionierte nicht.

Code:

def isprime(number): print "Reticulating Splines..." fnum=[1,] notprime=0 for p in range(2, number): if (number % p) == 0: notprime=1 fnum.append(p) continue if notprime == 1: return number, "is not a prime because of these factors", fnum else: return True num =int(raw_input("Enter number: ")) print isprime(num) 

Ausgabe:

 Enter number: 12 Reticulating Splines... (12, 'is not a prime because of these factors', [1, 2, 3, 4]) >>> Enter number: 25 Reticulating Splines... (25, 'is a prime number') 

Erwartete Ausgabe:

 Enter number: 12 Reticulating Splines... (12, 'is not a prime because of these factors', [1, 2, 3, 4, 6]) Enter number: 25 Reticulating Splines... (25, 'is not a prime because of these factors', [1,5]) 

Schlechte Kontrolle Struktur ist meine Vermutung, aber kann jemand meinen Code reparieren?

Ich verstehe, wie range () funktioniert: In diesem Fall range () wird ein Start- und ein Stop-Wert gegeben, Schritt standardmäßig auf 1. Ich verstehe das weiter, setzt eine Schleife fort, aber kann ich es mit if verwenden? Ich denke, das ist falsch

AKTUALISIEREN
Gelöst, Problem mit Einzug der Fortsetzung sollte für die for-Schleife gewesen sein, dito für die if … notprime.

 def isprime(number): print "Reticulating Splines..." fnum=[1,] notprime=0 for p in range(2, number): if (number % p) == 0: notprime=1 fnum.append(p) if notprime == 1: return number, "is not a prime because of these factors", fnum else: return number, "is a prime number" num =int(raw_input("Enter number: ")) print isprime(num) 

Update2: (Thx zu @neil)
Und der continue ist einfach dumm

Aktualisierter Code und Geschwindigkeitsvergleiche zwischen n / 2 und sqrt (n) Dank @neil und @emmanuel
N / 2 code: v2

 import time def isprime(number): start=time.clock() print "Reticulating Splines..." fnum=[1,] notprime=0 for p in range(2, (number/2)+1): if (number % p) == 0: notprime=1 fnum.append(p) end=time.clock() if notprime == 1: return number, "is not a prime because of these factors", fnum, "Time taken", end-start else: return number, "is a prime number. Time Taken", end-start print "Prime or factor calculator v2 using n/2" print # num =int(raw_input("Enter number: ")) print isprime(num) 

Sqrt (n) Code: v3

 import math, time def isprime(number): start=time.clock() print "Reticulating Splines..." fnum = [1,] last = int(math.ceil(math.sqrt(number))) for p in range(2, last + 1): if (number % p) == 0: fnum.append(p) fnum.append(number / p) # Remove duplicates, sort list fnum = list(set(fnum)) fnum.sort() end=time.clock() if len(fnum) > 1: return number, "is not a prime because of these factors", fnum ,"Time taken", end-start else: return True, "Time taken", end-start print "Prime or factor calculator v3 using sqrt(n)" print # num =int(raw_input("Enter number: ")) print isprime(num) 

Ausgabe (nur Zeit anzeigen)

Zeit für sqrt (n) Code: v3
Prime oder Faktor Rechner v3 mit sqrt (n)
Nummer eingeben: 999999
Zeit genommen ', 0.0022617399697466567

Zeit für n / 2 Code: v2
Prime oder Faktor Rechner v2 mit n / 2
Nummer eingeben: 999999
Zeitaufwand: 0.11294955085074321

Zeit für ursprünglichen Code (n): v1
Prime oder Faktor Rechner v1
Nummer eingeben: 999999
Zeitaufwand: 0.22059172324972565

V1 und v2 konnten die Nummern 999999999, 999999999999 und 999999999999999 nicht verarbeiten, beide gaben einen MemoryError

Allerdings hat v3 die drei Zahlen behandelt:
999999999: 0,010536255306192288
999999999999: 0.75631930873896636
999999999999999: 24,04511104064909

Die Shell hängt für 9999999999999999 und gibt einen MemoryError für 999999999999999999

Danke an @Lennart, denke ich daran, den Code in einer mehr OOP freundlichen Weise zu schreiben, indem ich Klassen verwende. Aber ich scheine es nicht richtig zu machen.

4 Solutions collect form web for “Berechnen Sie alle möglichen Faktoren einer Primzahl”

Das Problem ist deine Einrückung – if notprime==1: sollte nicht innerhalb der for-Schleife sein. Es sollte nur eine Einzugsstufe haben.

Auch die continue ist unnötig.

BEARBEITEN:

Eine Verbesserung, die Sie machen können (ich arbeitete gerade an Primzahlen letzte Nacht für ein Projekt Euler Problem) ist nur Schleife zu n / 2 – es kann nicht ein Faktor größer als die Hälfte der Zahl sein.

Ihr Finale, if notprime ... und die drei Zeilen, die darauf folgen, sind zu weit eingerückt und als solche wird in der Schleife ausgeführt, anstatt von außen.

Sie kehren nach dem Testen nur einer Nummer zurück. Bewegen Sie die if-Tests und die Rückkehr nach außerhalb der for-Schleife.

Auch wenn man True wenn es eine Primzahl ist und ein String, wenn es nicht ist, ist unpraktisch. Wenn du dann anrufst

 if isprime(7): 

Das wird immer als True ausgewertet. Ich habe die Dinge etwas verbessert:

 def factors(number): fnum=[] for p in range(2, number): if (number % p) == 0: fnum.append(p) return fnum for x in range(100): f = factors(x) if f: print x, "is not a prime and has factors", f else: print x, "is a prime" 

@neil:

"Eine Verbesserung, die du machen kannst … ist, nur zu n / 2 zu schleifen – es kann nicht ein Faktor größer als die Hälfte der Zahl sein."

Übrigens ist der höchste Wert, den du testen musst, int(math.ceil(math.sqrt(n))) , keine Notwendigkeit, zu n/2 zu gehen, wenn jedes Mal, wenn du einen Wert bekommst, bekommst du die dazugehörigen (dh Wenn axb = n , ist entweder a oder b niedriger als die Quadratwurzel von n und die andere ist größer):

 def isprime(number): print "Reticulating Splines..." fnum = [1,] last = int(math.ceil(math.sqrt(number))) for p in range(2, last + 1): if (number % p) == 0: fnum.append(p) fnum.append(number / p) # Remove duplicates, sort list fnum = list(set(fnum)) fnum.sort() if len(fnum) > 1: return number, "is not a prime because of these factors", fnum else: return True 

Größere Leistung, auch wenn am Ende die Liste nicht sortiert ist (aber dies kann innerhalb der Schleife durchgeführt werden, indem man die 2 Zahlen p und number / p an den guten Indizes addiert).

  • Sieve von Eratosthenes - Finding Primes Python
  • Iterate alle coprime Paare mit konstantem Raum?
  • Erklären Sie einen Code, um die Primalität auf der Grundlage von Fermats kleinem Theorem zu überprüfen
  • Finden der n-ten Anzahl von Primzahlen
  • Entfernen von Nicht-Primzahlen aus der Liste
  • Radfaktorisierung zu einem unbestimmten Sieb hinzufügen
  • Faktorisierung einer Zahl in Python
  • Circular Prime Zahlen Falsches Ausgabe-Python-Programm
  • Programm, um die n-ten Primzahl zu finden
  • Überprüfen, ob eine Zahl eine Primzahl in Python ist [doppelte]
  • Python prime numbers Sieve von Eratosthenes
  • Python ist die beste Programmiersprache der Welt.