Primzahlentester als rekursives Programm!

Status
Nicht offen für weitere Antworten.
G

gateway_2_hell

Gast
Hallo!

Ich sitze im Moment an dieser Aufgabe:

Exercise 1

A prime number is an integer that cannot be divided by any integer other than one and itself. For example, 7 is prime because its only divisors are 1 and 7. The integer 8 is not prime because its divisors are 1, 2, 4, and 8.

Another way to define prime is:

prime(N) = prime(N, N-1)

prime(N, 1) = true

prime(N, D) = if D divides N, false
else prime(N, D-1)

For example,

prime(4) = prime(4,3)
prime(4,3) = prime(4,2)
prime(4,2) = false

Another example,

prime(7) = prime(7,6)
prime(7,6) = prime(7,5)
prime(7,5) = prime(7,4)
prime(7,4) = prime(7,3)
prime(7,3) = prime(7,2)
prime(7,1) = true

Translate the math-like definition of prime into two Java methods that return boolean. Use the % operator to test divisibility. Put your method into a class, write a testing class, and test your program. (Look at FactorialTester.java in this chapter.)

If you run your program for integers larger than about 12,000 (on a Windows system) you will run out of memory. Your program will stop running and report a StackOverflowError. This is because each activation in the activation chain requires some memory, and 12,000 activations uses up all the memory that has been reserved for this use.


Es geht darum, einen rekursiven "Primzahlentester" zu schreiben.

Code:
public class PrimeTester
{
private prime prim;

	public boolean PrimeTester(int N)
	{
		prim = new prime();
		return prim.istPrimzahl(N, N-1);
	}

	
}

Code:
public class prime
{
    
    public boolean istPrimzahl(int N, int D)
    {
        boolean rg = true;
        
        if(N == 1)     // Eins ist keine Primzahl! 
            rg = false;
        
        if(D == 1)
            rg=true;
        
        else if (N % D == 0)   //Wenn sie Teilbar ist, ist die Zahl auch keine Primzahl / Bei N=1 stürzt das Programm hier ab (Division durch 0...)
            rg = false;
        
        else
            rg = istPrimzahl(N, D-1);
        
        return rg;
     }
    
     
    
}



So weit bin ich im Moment. Das Programm funktioniert auch schon, nur ein Sonderfall ist noch nicht bedacht: N = 1. In diesem Fall soll ja false zurückgegeben werden.
Ich möchte das Programm möglichst mit nur einem Ausgang (--> return) schreiben.
Kann mir wer nen Tipp geben?

Vielen Dank für eure Hilfe![/code]
 

norman

Top Contributor
warum soll es nur ein return geben? wenn d=1 ist brauchst du doch die anderen sachen nicht mehr testen?
[edit] n durch d ersetzt
 
G

Gast

Gast
Jo da haste ja recht...

Mein Infolehrer meint es wäre vom "Laufzeitverhalten" besser :D

Ich könnt auch einfach nen 2. return reinschreiben... Wäre einfacher.. sollen wir aber nich...
 

norman

Top Contributor
habs nicht weiter getestet, aber:
Code:
public class Test {
	
	public static boolean primeTest(int zahl) {
		return isPrime(zahl, zahl-1);
	}
	
	public static boolean isPrime(int n, int d) {
		boolean isPrime=false;
		
		if (n==1) {
			isPrime=false;
		} else if (d==1) {
			isPrime=true;
		} else if (n%d==0) {
			isPrime=false;
		} else isPrime(n, d-1);
		
		return isPrime;
	}
	
	public static void main(String args[]) {
		System.out.println(primeTest(1));
	}            
}
 
G

Gast

Gast
:D

Danke norman! Gute Idee, an die Stelle ein else zu packen :)


Danke an alle :)
 

norman

Top Contributor
btw: was ist das denn für ein algorithmus? denke es gibt da bessere um zu prüfen ob es eine primzahl ist ???:L
 

norman

Top Contributor
denke das war so noch nicht richtig. hier eine richtige lösung denke ich:
Code:
public class Test {
	
	static boolean isPrime;
	
	public static boolean primeTest(int zahl) {
		return isPrime(zahl, zahl-1);
	}
	
	public static boolean isPrime(int n, int d) {		
		if (n==1) {
			isPrime=false;
		} else if (d==1) {
			isPrime=true;
		} else if (n%d==0) {
			isPrime=false;
		} else isPrime(n, d-1);
		
		return isPrime;
	}
	
	public static void main(String args[]) {
		System.out.println(primeTest(127));
	}            
}
frag mich trotzdem wer sich den algorithmus überlegt hat ???:L
 

RicoSoft

Aktives Mitglied
immer noch falsch...

Code:
public class Test {
   
   static boolean isPrime;
   
   public static boolean primeTest(int zahl) {
      return isPrime(zahl, zahl-1);
   }
   
   public static boolean isPrime(int n, int d) {      
      if (n==1) {
         isPrime=false;
      } else if (d==1) {
         isPrime=true;
      } else if (n%d==0) {
         isPrime=false;
      } else isPrime(n, d-1);
      
      return isPrime;
   }
   
   public static void main(String args[]) {
      System.out.println(primeTest(127));
   }           
}

Aber der Algorithmus ist echter Blödsinn.
 

RicoSoft

Aktives Mitglied
ahhhh, ich hab den code ja gar nicht korrigiert. die letzte Abfrage
Code:
isPrime = isPrime(n, d-1);
 
B

bygones

Gast
norman hat gesagt.:
sehe das problem immernoch nicht? mit welcher (prim)zahl funktioniert mein code nicht? :shock:
ein schlechter algorithmus muss nicht unbedingt ein falsches ergebnis liefern.

gehen wir mal den Algorithmus mit 127 durch

1. isPrime(127,126) -> testen auf 127 % 126 == 0 ? false
2. isPrime(127,125) -> testen auf 127 % 125 == 0 ? false
usw. usw

es sind einfach zu viele Tests v.a. von der falschen seite herangehend.

von unten anfangen - z.b. 2. Beispiel: testen von 128. es dauert bis 64, bis du ein true erhälts. Mit dem Test von 2 hättest du das schon beim ersten Test erhalten. usw usw
 

norman

Top Contributor
deathbyaclown hat gesagt.:
es sind einfach zu viele Tests v.a. von der falschen seite herangehend.
klar, den algorithmus habe ich ja auch in frage gestellt. aber der war ja laut aufgabe vorgegeben :!: :arrow: guckst du
RicoSoft meinte nur, er würde nicht funktionieren - aber das kann ich nicht nachvollziehen.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Rekursives Programm zum Anzeigen von Primzahlen Java Basics - Anfänger-Themen 3
C Rekursives Backtracking beim Spiel Peg Java Basics - Anfänger-Themen 22
G Rekursives Programmieren --> harmonische Reihe Java Basics - Anfänger-Themen 3
S Rekursives Problem.... Java Basics - Anfänger-Themen 16
S Rekursives Durchlaufen eines Verzeichnisses - AccessDeniedException behandeln Java Basics - Anfänger-Themen 1
S Rekursives Zählen einer Zahl Java Basics - Anfänger-Themen 8
J Rekursives Parsen (ohne Reg Expressions) Java Basics - Anfänger-Themen 8
S Rekursives Umdrehen, Spiegeln. etc. von Strings Java Basics - Anfänger-Themen 3
I Rekursives Löschen in Binärem Suchbaum Java Basics - Anfänger-Themen 2
L rekursives spiel programmieren Java Basics - Anfänger-Themen 4
G Rekursives aufrufen führt zu StackOverflowError Panel durchl Java Basics - Anfänger-Themen 5
M Rekursives suchen im TreeMenu Java Basics - Anfänger-Themen 10
N Rekursives suchen in einer Liste Java Basics - Anfänger-Themen 8
H Rekursives einlesen von Lokalen Ordner Java Basics - Anfänger-Themen 4
J Delay erzeugen, ohne Programm zu blockieren Java Basics - Anfänger-Themen 7
Ü Dead Code im Programm? Java Basics - Anfänger-Themen 13
M Java Mail Programm Java Basics - Anfänger-Themen 4
E Java Programm zur anzeige, ob Winter- oder Sommerzeit herrscht Java Basics - Anfänger-Themen 62
M Mini Jar-Programm Java Basics - Anfänger-Themen 51
G JTable Listselectionlistener friert das Programm ein Java Basics - Anfänger-Themen 8
M Das Programm stellt nichts dar Java Basics - Anfänger-Themen 2
K Programm compilierbar aber nicht ausführbar... Java Basics - Anfänger-Themen 21
Z Programm Ideen Java Basics - Anfänger-Themen 8
P Wie kann ich in meinem Java Programm etwas dauerhaft speichern? Java Basics - Anfänger-Themen 5
P Wie kann ich beispielsweise Speicherstände eines Spiels DAUERHAFT in meinem Programm speichern? Java Basics - Anfänger-Themen 3
H Java-Programm zur Ausgabe von Zuständen Java Basics - Anfänger-Themen 80
G Kann Java-Programm nicht als jar aufrufen, auch als EXE nicht Java Basics - Anfänger-Themen 19
benny1993 Java Programm erstellen für ein Fußball-Turnier Java Basics - Anfänger-Themen 3
T Programm stürzt ab Java Basics - Anfänger-Themen 40
KeinJavaFreak Erste Schritte Programm "Java(TM) Platform SE binary " nicht vorhanden Java Basics - Anfänger-Themen 1
G Programm läuft durch, ohne Eingabe aus dem Chat abzuwarten Java Basics - Anfänger-Themen 4
N Programm Funktioniert mit .txt Datei aber nicht mit .rtf Datei Java Basics - Anfänger-Themen 2
N Interpreter-Fehler Compiler zeigt keine Fehler an, aber das Programm läuft nicht (BlueJ) Java Basics - Anfänger-Themen 2
D Java Programm mit Batch-Datei starten Java Basics - Anfänger-Themen 32
Jul1n4tor Programm mit Scanner und If-Statements Java Basics - Anfänger-Themen 2
D Wie sehe ich ein Java-Programm? Java Basics - Anfänger-Themen 27
K Ist das Programm schlecht bzw. schlampig programmiert ? Java Basics - Anfänger-Themen 9
Zrebna Kann Java Programm nicht in Konsole ausführen Java Basics - Anfänger-Themen 1
K Warum läuft das Programm nicht(bzw. nicht richtig) Java Basics - Anfänger-Themen 4
M Von Eclipse zum richtigen Programm Java Basics - Anfänger-Themen 1
nbergmann IntelliJ: Wie lade ich ein fertiges Programm aus dem Lehrbuch? Java Basics - Anfänger-Themen 26
D Anfängerfrage zu meinem Programm. Java Basics - Anfänger-Themen 15
nbergmann Eclipse: Lehrbuch-Programm startet nicht Java Basics - Anfänger-Themen 22
I Jetty starten von Programm (Main) Java Basics - Anfänger-Themen 27
Kydo Programm Beschreibung Java Basics - Anfänger-Themen 3
nbergmann Eclipse: Lehrbuch-Programm startet nicht Java Basics - Anfänger-Themen 7
T Java FXML selbes Fenster verschiedene Stellen im Programm Java Basics - Anfänger-Themen 5
frager2345 Programm erstellen ohne Autoboxing und Unboxing Java Basics - Anfänger-Themen 13
D JAVA Programm schreiben Java Basics - Anfänger-Themen 46
P exportiertes Programm funktioniert nur teilweise Java Basics - Anfänger-Themen 7
J Mein Programm läuft bei der ersten Eingabe nicht mehr weiter, woran liegt das? Java Basics - Anfänger-Themen 6
M Wo hält das Programm an? Java Basics - Anfänger-Themen 11
J Mein Java Programm lässt sich nicht mehr bearbeiten Java Basics - Anfänger-Themen 2
Fugover Programm funktioniert nicht Java Basics - Anfänger-Themen 11
Fugover Kopfrechnen-Programm Java Basics - Anfänger-Themen 6
NadimArazi Wie kann ich eine collision detection für die Paddles in meinem Pong Programm hinzufügen? Java Basics - Anfänger-Themen 4
sserio Wieso funktioniert mein Programm nicht Java Basics - Anfänger-Themen 2
sserio Größtes Palindrom-Produkt Programm funktioniert nur halb Java Basics - Anfänger-Themen 23
J selbst erstellte Datei mit Programm öffnen Java Basics - Anfänger-Themen 10
F nach Methode Programm nicht beenden Java Basics - Anfänger-Themen 9
A wie kann ich es in meinem Programm rein tun Java Basics - Anfänger-Themen 8
S Fehler beim Programm Java Basics - Anfänger-Themen 2
Jose05 Fehler im Programm feststellen Java Basics - Anfänger-Themen 2
F Kann mir jemand kurz dieses Programm erklären? Java Basics - Anfänger-Themen 22
I Programm erkennt nicht an das Array zurückgegeben wird trotz Initialisierung *einfach* Java Basics - Anfänger-Themen 9
J Nach dem Exportieren funktioniert mein Programm nicht mehr Java Basics - Anfänger-Themen 8
P Mein Programm wird zwar erfolgreich Compiliert, öffnet sich aber nicht Java Basics - Anfänger-Themen 6
J Kann ich mein Programm so schreiben? Java Basics - Anfänger-Themen 4
A Lotto Programm Java Basics - Anfänger-Themen 3
S Programm erstellen Java Basics - Anfänger-Themen 3
A Verarbeiten einer Excel Datei durch das java-Programm Java Basics - Anfänger-Themen 3
S MinMax Programm erstellen Java Basics - Anfänger-Themen 4
J Interpreter-Fehler Programm gibt nicht gewünschtes Ergebnis aus Java Basics - Anfänger-Themen 11
brypa Programm mit Eingabe Java Basics - Anfänger-Themen 129
B Java Programm soll mit Python kommunizeren Java Basics - Anfänger-Themen 1
SpigBin Programm läuft nicht weiter... Java Basics - Anfänger-Themen 10
M JAVA Programm in Website einbinden Java Basics - Anfänger-Themen 19
B Programm, dass alle 3 Tage eine Webseite öffnet? Java Basics - Anfänger-Themen 20
B Programm beendet sich nicht und weiteres seltsames Verhalten Java Basics - Anfänger-Themen 9
N Eclipse Programm normal ausführen Java Basics - Anfänger-Themen 1
D Programm auf Enter warten lassen Java Basics - Anfänger-Themen 2
C Programm das feststellen kann, ob eine eingegebene Zahl einem Schaltjahr entspricht, richtig geschrieben? Java Basics - Anfänger-Themen 11
C Brauche Hilfe um ein Programm zu schreiben Java Basics - Anfänger-Themen 8
F Frage betreff Programm mit dem man C++-Code in JAVA-Code übersetzen lassen kann Java Basics - Anfänger-Themen 2
nevel Programm für die Summer der Zahlen 1- 1ß Java Basics - Anfänger-Themen 12
WAB9703-04 Programm zum automatischen Ausfüllen von Formularen programmieren Java Basics - Anfänger-Themen 3
OSchriever Jar-Programm läuft auf Windows aber nicht auf Linux(Raspberri Pi4) Java Basics - Anfänger-Themen 22
G Programm Code Java Basics - Anfänger-Themen 5
CptK Achsenskalierung in Koordinatensystem hängt Programm auf Java Basics - Anfänger-Themen 5
H Kann eine while-Schleife ein Programm blockieren? Java Basics - Anfänger-Themen 8
TimoN11 Mail Programm mit Java? Java Basics - Anfänger-Themen 1
Sajeel Chattha Dieses Programm umschreiben Java Basics - Anfänger-Themen 5
J Programm beenden ohne System.exit() oder Runtime.exit() Java Basics - Anfänger-Themen 5
F Java Programm, das kleine Buchstaben in einem String zählen soll und bei großen Buchstaben oder Sonderzeichen abbrechen soll. Java Basics - Anfänger-Themen 5
A Programm Histogram Java Basics - Anfänger-Themen 2
C Was ist nötig für ein Java-Programm auf Server für Website Java Basics - Anfänger-Themen 18
CT9288 Interaktion mit laufendem Programm -Fachbegriffe Java Basics - Anfänger-Themen 2
Gaudimagspam Assertions im Programm hinzufügen Java Basics - Anfänger-Themen 4
G Weiß jemand wie man dieses Programm schreibt? Java Basics - Anfänger-Themen 84
C Programm ausführen ohne JRE? Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben