# primzahl oder nicht?



## gast (12. Nov 2003)

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?


----------



## bygones (12. Nov 2003)

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 (12. Nov 2003)

nee du, das is quark.

der algo is simpel:

```
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.


----------



## bygones (12. Nov 2003)

*kopfkratz* - dann habe ich da wohl mal was falsch verstanden -sorry...


----------



## Mick (12. Nov 2003)

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 (13. Nov 2003)

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 (13. Nov 2003)

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 (13. Nov 2003)

cool danke ich werde mich an eure tips halten. wenn ich noch was wissen muss meld ich mich noch mal


----------



## newbee (16. Nov 2003)

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?

```
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 + "  ");
    }
  }
}
```


----------



## Guest (20. Nov 2003)

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.


----------



## Gast (20. Nov 2003)

Also, ich habe den Algorythmus für dich geschrieben:
(Du kannst ihn verwenden, wenn du willst)

```
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.


----------



## Guest (20. Nov 2003)

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 (20. Nov 2003)

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 (21. Nov 2003)

@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:

```
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:

```
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


----------



## Guest (22. Nov 2003)

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 (22. Nov 2003)

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.


----------



## Gast (23. Nov 2003)

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.


----------

