primzahl oder nicht?

Status
Nicht offen für weitere Antworten.
G

gast

Gast
hallo, wie kann ich ein programm schreiben, das eine eingegebene zahl prüft, ob es eine primzahl ist.
da muss ich doch überprüfen, ob sie durch sich selber teilbar ist und durch 1?
mach ich das nur mit einer if anweisung?
 
B

bygones

Gast
jede Zahl ist durch sich oder 1 teilbar. Was du zeigen musst, ist dass es keine anderen Zahlen gibt, die deine Zahl teilen.

Wenn mich mein informatisches Wissen nicht ganz im Stich lässt würde ich dir davon abraten, da das Problem der Primzahlen bzw. Faktorenzerlegung semi-entscheidbar ist.

D.h. du wirst keinen Algorithmus findet, der für jede eingegebene Zahl in endlicher Zeit termniniert. D.h. es kann sein dass er terminiert und dir sagt ob es eine primzahl ist, es kann aber auch sein, dass er nicht terminiert (hoffe das ist verständlich).

Auf gut deutsch, das Problem hatte / haben viele und es gibt meines Wissens keinen Algorithmus der es lösen kann...

Stimmt doch, oder ?
 

schalentier

Gesperrter Benutzer
nee du, das is quark.

der algo is simpel:
Code:
input: zahl x
output: x ist prim/ nicht prim

zahl gerade? --> x ist nicht prim
für alle zahlen i von 3 bis sqrt(x)+1:
  (x mod i)==0 --> x ist nicht prim
--> x ist prim

dieser algorithmus terminiert immer, nach endlicher zeit und liefert prim/nicht prim zurück.
 

Mick

Bekanntes Mitglied
deathbyaclown hat gesagt.:
*kopfkratz* - dann habe ich da wohl mal was falsch verstanden -sorry...

Es gibt keinen effizienten Algorithmus, mit dem man riesige Primzahlen erechnen kann. Das meintest Du wahrscheinlich. Das ist immer noch ein Problem, was die Wissenschaft beschäftigt.

Grüße,
Mick
 

gustav

Aktives Mitglied
Also für kleine Primzahlen sollte doch die einfache Iterative Methode von schaltentier
genügen. Wenn die Zahlen größer werden, dann mußt Du hier auch mehr Zeit investieren (wenigstens Wurzel n Schleifendurchläufe und dann noch aufwendig dividieren).
Jedenfalls ist z.Z. noch kein Algo bekannt der das Problem in vertretbarer Zeit und zu 100% vollständig lösen kann (hat auch was mit P=NP zu tun). Aber es geht auch schneller, informier Dich z.B. mal über den MillerRabin Test. Der Test gibt mit einer Wahrscheinlichkeit von xxx eine Antwort auf die Primzahlfrage. Wenn man ihn dann mehrmals hintereinander erfolgreich ausführt erhöht sich auch die Wahrscheinlichkeit eine Primzahl gefunden zu haben......
 

Nobody

Top Contributor
zum beitrag vom schalentier: es müssen dabei die zahl nur durch die kleineren primzahlen geteilt werden. diese musst du entweder speichern oder kannst das ganze zu einer suche zwischen 4 und x (G= x€N>5) oder einer suche zwischen x und y verwendet werden (G=x€N>3;y€N>4^y>x).
 

newbee

Mitglied
hi hab follgemdes proggi gemacht aber noch fehler drinn. ab 49 sagt er mir es ist eine primzahl obwohl ws keine ist und er soll mir den kleinsten teiler ausgeben wenn keine prim. wie geht das?
Code:
import java.io.*;

public class Primzahl {
  
  public static void main(String[] args) throws IOException {
    
    BufferedReader in = new BufferedReader(
                          new InputStreamReader(System.in));
    
    String x;    
    System.out.println("Positive ganze Zahl eingeben:");
    x = in.readLine();
    int zahl = Integer.parseInt(x);
    
    boolean istPrim = true;  
    int teiler = 1;         
    
    if (zahl % 2 == 0) { 
      istPrim = false;
      teiler = 2;
    }
    
    
    if (istPrim) {
      System.out.println(zahl + " ist eine Primzahl");
    } else {
      System.out.println(zahl + " ist keine Primzahl, aber der kleinste teiler ist: " + teiler + "  ");
    }
  }
}
 
G

Guest

Gast
Ich weiss ja nicht, aber du prüfst gar nicht, ob es eine Primzahl ist oder nicht. Du prüfst nur, ob die Zahl gerade oder ungerade ist. Das kann nicht funktionieren.
 
G

Gast

Gast
Also, ich habe den Algorythmus für dich geschrieben:
(Du kannst ihn verwenden, wenn du willst)
Code:
public class CPrim
{
 public static void main(String[] args)
 {

  String parameter = args[0]; //Einlesen von Zahl
  int zahl = Integer.parseInt(parameter);

  System.out.println("Es wird geprueft, ob "+zahl+" eine Primzahl ist.");

  boolean istgerade = false;

  int rest = zahl % 2;

  if(zahl != 2)
  {
   if(rest == 0)
   {
    istgerade = true;
    System.out.println("Sie haben eine gerade Zahl eingegeben.");
   }
  }

  if(!istgerade)
  {
   int anzahl_teiler = 0;
   for(int teiler = 1; teiler <= zahl; teiler++)
   {
    int rest_zwei = zahl % teiler;
    if(rest_zwei == 0)
    {
     anzahl_teiler++;
    }
   }
   if(anzahl_teiler == 2)
   {
    System.out.println(zahl+" ist eine Primzahl.");
   }
   else
   {
    System.out.println(zahl+" ist keine Primzahl.");
   }
  }
 }
}
Vielleicht möchtest du die Eingabeart verändern oder noch einen Schutz gegen negative Zahlen einbauen.
Viel Spass.
 
G

Guest

Gast
Der Algorythmus ist mehr oder weniger schnell. Für grosse Zahlen muss man jedoch lange warten. Es gibt auch noch einen anderen Fehler, der mir erst jetzt aufgefallen ist. Natürlich solltest du anstelle von Integer Double-Zahlen verwenden. Du musst also den Quellcode noch ein bischen abändern.
 

Nobody

Top Contributor
ich sass vor kurzem dran und wartete auf meinen zug da kam mir was in den kopf:
die schnellste methode ist das ganze aus einer datei auszulesen. nun darauf bin ich gekommen, da ich grad ka warum an maple denken musste und dann fiel mir auf, dass die so pi "bestimmen". das ganze packt man einfach in ein array rein und fragt die eingegebene zahl ab, ob sie gleich einem der angegeben typen ist und voila das ganze funktioniert recht flott.
 

schalentier

Gesperrter Benutzer
@nobody: wenn du alles vorher ausrechnest, brauchst du viel speicher und zeit, alles vorher zu berechnen. is also nich wirklich nützlich.

@gast1: wieso double? prim können nur zahlen aus N (natürliche Zahlen) sein!

@gast2:
- es reicht bis wurzel(zahl) auf teilbarkeit zu testen
- brauchst nur ungerade zahlen testen (teiler+=2)

@all:
hier mal der algo, um große zahlen auf prim zu testen:
Code:
import java.math.BigInteger;
import java.util.Random;

public class RMA
{
    static BigInteger TWO = BigInteger.valueOf(2);
    static BigInteger NEG_ONE = BigInteger.valueOf(-1);

    public static boolean primRMA( BigInteger n, int I )
    {
        BigInteger u = n.subtract(BigInteger.ONE);
        BigInteger q = BigInteger.ZERO;
        BigInteger n_2 = n.subtract(TWO);
        BigInteger n_1 = n.subtract(BigInteger.ONE);

        while( !u.testBit(0) ) // n-1 = u*2^q
        {
            u = u.shiftRight(1);
            q = q.add(BigInteger.ONE);
        }

        BigInteger a,j,b=BigInteger.ZERO;
        do
        {
            a = random( TWO, n_2 );
            I--;
            j = BigInteger.ONE;
            b = a.modPow(u,n);
            if( b.compareTo(BigInteger.ONE)!=0 )
            {
                while( b.compareTo(n_1)!=0 && j.compareTo(q)<=0 )
                {
                    b = b.multiply(b).mod(n);
                    j = j.add(BigInteger.ONE);
                }
                if( b.compareTo(n_1)!=0 ) return false;
            }
        } while( (b.compareTo(BigInteger.ONE)==0||b.compareTo(n_1)==0) && I>0 );
        return (b.compareTo(BigInteger.ONE)==0||b.compareTo(n_1)==0);
    }
    static Random seed = new Random();

    public static BigInteger random( BigInteger min, BigInteger max )
    {
        BigInteger R;
        do
        {
            R = new BigInteger(max.bitLength(), seed).add(min);
        } while( R.compareTo(max)>0 );
        return R;
    }

    public static void main( String[] args )
    {
        int int_n = 192229;
        System.out.println( int_n+" prim: "+primRMA( BigInteger.valueOf(int_n), 8 ) );
    }
}
es handelt sich um den RABIN-MILLER test. dieser basiert auf dem kleinen satz von fermat:
wenn n prim, dann gilt:
Code:
a^(n-1) = 1 (mod n)
für alle a von 1..(n-1)

der algo klappt nur für ungerade zahlen als eingabe (int_n). je größer die zahl, desto wahrscheinlicher ist das ergebnis korrekt. für zahlen größer 256bit ist sie bei einer iteration größer als das ein fehler in der hardware das ergebnis verfälscht.

viel spass damit
 
G

Guest

Gast
Ich weiss, dass Primzahlen nur vom Typ Ganzzahl sein können. Wenn man jedoch im Algorythmus Integer durch Double ersetzt, kann man viel grössere Zahlen berechnen. Mit Integer kann man nur Zahlen bis zu +/- 2147483647 wenn man jedoch Double verwendet kann man ca. bis +/- 1.79E308 rechnen.
 

schalentier

Gesperrter Benutzer
Aber mit doubles kann man nicht Modulus rechnen, oder?

Für große ganzzahlige Zahlen nimmt man BigInteger, der hat soweit ich weis keine beschränkung des Zahlenbereichs.
 
G

Gast

Gast
Doch mit Double kann man modulo rechnen. Ist eine normale Funktion. Man darf halt keine Zahlen wie 10.11112 oder so eingeben, aber wer mach das schon????
10.0 % 2 ergibt jedoch auch 0. Wenn du das mit Integer rechnest 10 % 2 ergibt es auch 0. Es macht keinen Unterschied.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
C Ganzzahlige Werte in Boolean ausgeben und überprüfen ob Primzahl oder nicht, wenn es keine Primzahl ist soll es die Primfaktorzerlegung ausgeben Java Basics - Anfänger-Themen 4
F Primzahl oder nicht?! Java Basics - Anfänger-Themen 7
P Primzahl mit Angabe der höchsten Primzahl und Angabe der Anzahl von Primzahlen bis 100 Java Basics - Anfänger-Themen 8
O Primzahl rekursiv mit einem Wert ohne i, wie? Java Basics - Anfänger-Themen 6
O Erste Schritte Primzahl Methode Java Basics - Anfänger-Themen 8
I Erste Schritte Testen, ob eine Zahl eine Primzahl ist Java Basics - Anfänger-Themen 8
O Primzahl bis n Java Basics - Anfänger-Themen 5
D Primzahl Aufgabe Java Basics - Anfänger-Themen 5
R Primzahl ja/nein - besserer Code möglich? Java Basics - Anfänger-Themen 2
T Primzahl Java Basics - Anfänger-Themen 12
I Höchste Zahl berechnen die eine Eingabe ohne Rest teilt und eine Primzahl ist Java Basics - Anfänger-Themen 2
U Primzahl-Tester Java Basics - Anfänger-Themen 3
A 10001-te Primzahl herausfinden Java Basics - Anfänger-Themen 5
L primzahl Java Basics - Anfänger-Themen 54
R Primzahl kleiner 3 Java Basics - Anfänger-Themen 2
T Primzahl Schleife Java Basics - Anfänger-Themen 15
X Primzahl Ausgabe falsch Java Basics - Anfänger-Themen 10
M Primzahl Java Basics - Anfänger-Themen 11
D Array Fehler / groesste Primzahl suchen Java Basics - Anfänger-Themen 4
S Primzahl in einem Array finden Java Basics - Anfänger-Themen 21
J Primzahl mit for Schleife Java Basics - Anfänger-Themen 4
A Fehler im Primzahl Programm Java Basics - Anfänger-Themen 17
S Primzahl berechnen in Java Java Basics - Anfänger-Themen 7
K Primzahl//immer true Java Basics - Anfänger-Themen 7
ven000m Primzahl.class wie starte ich diese einzelne Datei? Java Basics - Anfänger-Themen 10
M Primzahl Java Basics - Anfänger-Themen 8
W Nächstgelegene Primzahl Java Basics - Anfänger-Themen 3
I Primzahl suchen Java Basics - Anfänger-Themen 5
richis-fragen JTable den angezeigten WERT nicht den Wert aus dem Model ausgeben. Java Basics - Anfänger-Themen 3
richis-fragen JTable Header ausgeblendete (width = 0) nicht per mouseDragged aufziehen. Java Basics - Anfänger-Themen 9
M Ausgabe einer ArrayList ensteht nur als Hashcode, nicht als Objekt Java Basics - Anfänger-Themen 16
K Warum wird mir auf der Konsole des Servers nicht "xxxx" angezeigt (Server/Client) Java Basics - Anfänger-Themen 4
K Warum wird hier nur etwas in eine txt Datei geschrieben und nicht in alle drei (InputStream/OutputStream/Reader/Writer) Java Basics - Anfänger-Themen 1
richis-fragen JTable effektiv angezeigter Text ausgeben nicht Inhalt vom Model Java Basics - Anfänger-Themen 9
S nach Import von jars (PLC4x) in Eclipse kann nicht mehr compiliert werden Java Basics - Anfänger-Themen 9
J Datenüberwachung funktioniert nicht Java Basics - Anfänger-Themen 9
S Wie debugge ich dies am besten: SingleThreadExecutor führt Task nicht aus..? Java Basics - Anfänger-Themen 29
H JDK installieren jdk-21 wird nicht erkannt Java Basics - Anfänger-Themen 13
N Klassen Hintergrundfarbe in JPanel ändert sich nicht Java Basics - Anfänger-Themen 3
K Warum wird mir "Empfangen vom Client:" nicht sofort ausgegeben(Server/Client) Java Basics - Anfänger-Themen 3
mo13 JTextField funktioniert nicht Java Basics - Anfänger-Themen 4
J .jar datei öffnen funktioniert nicht Java Basics - Anfänger-Themen 17
M Methode zielnah zeigt das gewünschte Ausgabe nicht an Java Basics - Anfänger-Themen 3
K Verstehe Rekursion nicht ganz Java Basics - Anfänger-Themen 7
M OOP Brüche nicht richtig berechnen Java Basics - Anfänger-Themen 3
N Ich kriege ganze zeit die Fehlermeldung "Inhalt der Zwischenablage kann nicht in die ausgewählten Elemente eingefügt werden" hat jemand eine Lösung? Java Basics - Anfänger-Themen 6
K TicTacToe belegtes feld nicht neu besetzbar Java Basics - Anfänger-Themen 1
K TicTacToe belegtes Feld nicht neu besetzbar Java Basics - Anfänger-Themen 3
A Warum wird mein jdk nicht gefunden? Java Basics - Anfänger-Themen 3
M Queue-Datenstruktur: nach dem Elementen entfernen, das Ergebnis ist immer noch nicht optimal. Java Basics - Anfänger-Themen 3
K Programm compilierbar aber nicht ausführbar... Java Basics - Anfänger-Themen 21
N Hey Leute und zwar versuche ich gerade ein 2D Spiel zu Programmieren aber die Figur will sich nicht nach links oder rechts bewegen :( Java Basics - Anfänger-Themen 12
G Mit jPackage erstellte EXE funktioniert nicht Java Basics - Anfänger-Themen 2
N BMI Rechner Was haltet ihr von dem Code habt ihr Verbesserungsvorschläge weil design teschnisch ist das nicht das geilste würde das gerne überarbeiten Java Basics - Anfänger-Themen 12
G Robot funktioniert nicht bei SelectionListener Java Basics - Anfänger-Themen 6
D MacOS: PDF erstellen geht nicht Java Basics - Anfänger-Themen 1
G Kann Java-Programm nicht als jar aufrufen, auch als EXE nicht Java Basics - Anfänger-Themen 19
J jar Befehl wird nicht erkannt Java Basics - Anfänger-Themen 7
missy72 Erste Schritte (nicht) Deterministischer endlicher Automat Java Basics - Anfänger-Themen 9
T Getter/Setter - wie sieht ein Setter aus? Und wie nicht? Java Basics - Anfänger-Themen 34
T catch(InputMismatchException) wird nicht ausgefürt/erkannt Java Basics - Anfänger-Themen 12
T Methode akzeptiert String nicht Java Basics - Anfänger-Themen 18
P Netbeans installation geht nicht Java Basics - Anfänger-Themen 26
R RegEx funktioniert nicht Java Basics - Anfänger-Themen 14
T HashMap Lsite gibt die sachen nicht aus wie gewollt. Java Basics - Anfänger-Themen 3
H Counter durch gepresste Taste nur auf 1 erhöhen und nicht durchzählen lassen Java Basics - Anfänger-Themen 7
S 2 Reihen ratio-btn, eine Reihe funktioniert andere nicht Java Basics - Anfänger-Themen 4
T scanner nicht erkannt Java Basics - Anfänger-Themen 3
monsterherz Punkt Notation funktioniert nicht Java Basics - Anfänger-Themen 4
monsterherz Fehler Semikolon fehlt - ich weiss aber nicht wo da noch eines hin sollte... Java Basics - Anfänger-Themen 21
R Java kann nicht installiert werden Java Basics - Anfänger-Themen 8
marcelnedza Finde meinen Fehler in einer Methode nicht, Java Karol Java Basics - Anfänger-Themen 15
monsterherz einfache Methode mit Fehler den ich nicht finde Java Basics - Anfänger-Themen 21
monsterherz if / else if mit Fehler den ich leider nicht finde Java Basics - Anfänger-Themen 11
D Jar Datei startet unter Linux nicht Java Basics - Anfänger-Themen 3
KeinJavaFreak Erste Schritte Programm "Java(TM) Platform SE binary " nicht vorhanden Java Basics - Anfänger-Themen 1
KeinJavaFreak Erste Schritte Java "Executable Jar File" nicht vorhanden Java Basics - Anfänger-Themen 1
M Konstruktor-Aufruf im Konstruktor, aber nicht am Anfang? Java Basics - Anfänger-Themen 4
G Variable aktualisiert sich nicht in rekursiver Methode Java Basics - Anfänger-Themen 4
Darkherobrine9 Import klappt nicht Java Basics - Anfänger-Themen 7
N Programm Funktioniert mit .txt Datei aber nicht mit .rtf Datei Java Basics - Anfänger-Themen 2
R Compiler-Fehler Variable wird nicht gefunden bzw. erkannt? Java Basics - Anfänger-Themen 2
_so_far_away_ Inventarisierungssystem brauche switch Cases und weiß nicht, wie ich e implementieren muss Java Basics - Anfänger-Themen 5
P BeforeEach AfterEach werden nicht ausgeführt. Java / Selenium Java Basics - Anfänger-Themen 4
I Erste Schritte Einfache Datenbank-Webseite erstellen als Nicht-IT-lerin Java Basics - Anfänger-Themen 24
N Interpreter-Fehler Compiler zeigt keine Fehler an, aber das Programm läuft nicht (BlueJ) Java Basics - Anfänger-Themen 2
D Quellcode für cmd funktioniert nicht Java Basics - Anfänger-Themen 9
C Kann mir jemand sagen warum ich nicht mal rechnen kann ? Java Basics - Anfänger-Themen 32
K Java Lotto Spiel; ich komme nicht weiter Java Basics - Anfänger-Themen 15
A JavaFX-Anwendung läuft nicht mit Selenium WebDriver Java Basics - Anfänger-Themen 0
T Meine Klasse wird nicht gefunden Java Basics - Anfänger-Themen 1
T Wie kann man es machen das ein Objekt nicht übermalt wird Java Basics - Anfänger-Themen 2
H Cast von Float nach String klappt nicht Java Basics - Anfänger-Themen 12
heinrich172 Methoden Trotz gleichem Element stimmt Vergleich nicht? Java Basics - Anfänger-Themen 7
I Entity Objekt nicht gefunden -> Webhook empfangen in der gleichen Methode (Transaktion) Java Basics - Anfänger-Themen 37
K warum kann ich das Objekt nicht erstellen ? Java Basics - Anfänger-Themen 2
MiMa Ungültiges Datum wird nicht erkannt ?? Java Basics - Anfänger-Themen 6
J Meine Mails gehen nicht raus Java Basics - Anfänger-Themen 8
Zrebna Kann Java Programm nicht in Konsole ausführen Java Basics - Anfänger-Themen 1
S Ist JDK jetzt free oder nicht? Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Neue Themen


Oben