[HaBo]

**Elderan** · 05.05.06, 22:11

Hallo,
es soll ein Programm geschrieben werden, welches überprüft, ob eine Zahl eine Primzahlen ist.

Dabei soll der User wählen, welchen Test er möchte:
1. Brute Force. Überprüfen ob die Zahl durch eine Zahl zwischen 2 und xxx Teilbar ist (Schleife). Optimiere diese Schleife bestmöglich.
2. Der kleine Satz von Fermat
3. Miller-Raben-Test
4. Ggf. noch andere Algorithmen

Zusatz #1:
Überprüfe, wie viele "falsche Primzahlen" die anderen Algorithmen zwischen 2 und xxxx (abhänig vom User) findet und gebe diese aus.

Zusatz #2:
Der User kann bei den Algorithmen bestimmen, wie viele "Zeugen" es geben soll. Zeuge bedeutet, wie oft die Zahl mit verschiedenen Basen getestet wurde (erhöht die Sicherheit der Aussage).

Zusatz #3:
Gebe von einer nicht Primzahl die Primfaktoren aus, am besten in einer exponentiellen Schreibweise.
Also 200: 2^3 * 5^2

Links:
Allg. Infos Primzahlen
Primzahlen 2 bis 100 000

Morgenroete · 31.05.06, 15:22

Aloha zusammen,

im Moment kämpfe ich mit einigen istreams und sockets... und die wollen einfach nicht. Seit 3 verdammten Tagen.

Nun wie dem sei, ich war so gefrustet, dass ich diese Aufgabe hier fand...

Das Programm ist gekapselt in drei Dateien, man verzeihe mir meine zum Teil englischen Kommentare, da diese generiert wurden :/.

Getestet ist es allerdings bisher nur mit kleinen Zahlen. Möglich sind Zahlen im Bereich unsigned long (ohne Einschränkung von 0 bis 4.294.967.295 [32bit]), (mit program. Einschränkung von 3 bis 4.294.967.295 [32bit]).

Ich hab das Ding gegen den Frust geschrieben, die Zusätze fehlen.

MfG,

Morgenroete

Code:

prim_main.cpp:

Code:

/*--------------------------------------------------------|
| primzahlen - Aufgabenstellung von                       |
|              http://www.hackerboard.de/thread.php?threadid=25173
|---------------------------------------------------------|
| folgende Aufgabenstellung:                              |
|   Dabei soll der User wählen, welchen Test er möchte:   |
|    1. Brute Force. Überprüfen ob die Zahl durch eine    |
|       Zahl zwischen 2 und xxx Teilbar ist (Schleife).   |
|       Optimiere diese Schleife bestmöglich.             |
|    2. Der kleine Satz von Fermat                        |
|    3. Miller-Raben-Test                                 |
|---------------------------------------------------------|
| fileinfo: prim_main.cpp - entrance point main and       |
|                           everything else.              |
|--------------------------------------------------------*/

#include "head.h"

int main()
{
    cout << "primzahlen - for Elderan - www.hackerboard.de\n";
    cout << "(C)opright by PD - visit www.pdhome.de\n\n";

    // buffer für Zahl:
    unsigned long ulZahl;

    do
    {
        cout    << "Bitte Zahl eingeben: ";
        cin     >> ulZahl;
        if(ulZahl <= 2)
            cout << "Bitte geben sie nur Zahlen > 2 ein.\n";

    }while(ulZahl <= 2);

    
    
    
    // auswahl:
    bool bChoice        = true;
    char cChoice;
    
    while(bChoice)
    {
        cout    << "\nMit welcher Art soll " << ulZahl << " auf eine Primzahl getestet werden: \n";
        cout    << "(0) Brute Force\n";
        cout    << "(1) Der kleine Satz von Fermat\n";
        cout    << "(2) Miller-Rabin-Test\n";
        cout    << "[0/1/2]: ";

        cin     >>    cChoice;

        switch(cChoice)
        {
        case '0':
            {
            // do BruteForce
             
                unsigned long ulDurchgaenge;
                cout << "Wieviele Durchgaenge wollen sie? (Tipp: Wurzel aus zu testender Zahl) ";
                cin >> ulDurchgaenge;

                if(DoBruteForce(ulDurchgaenge, ulZahl))
                    cout << "Ihre eingegebene Zahl koennte eine Primzahl sein,\noder sie ist groesser als ihre Brute Force Attack aufdecken konnte.\n";
                else
                    cout << "Ihre eingegebene Zahl ist keine Primzahl.\n";
                bChoice = false;
                break;
            }
        case '1':
            {
            // do Fermat
               if(DoFermat(ulZahl))
                   cout << "Ihre eingegebene Zahl ist eine (Pseudo-)Primzahl.\n";
               else
                   cout << "Ihre eingegebene Zahl ist keine Primzahl.\n";
    
                bChoice = false;
                break;
            }
        case '2':
            {
                // do Miller
                if(DoMiller(ulZahl))
                    cout << "Ihre eingegebene Zahl ist mit 3:4 wahrscheinlich eine Primzahl.\n";
                else
                    cout << "Ihre eingegebene Zahl ist wahrscheinlich keine Primzahl.\n";

                bChoice = false;
                break;
            }
        }

    }

    system("PAUSE");
    return 0;
}

prim_func.cpp:

Code:

/*--------------------------------------------------------|
| primzahlen - Aufgabenstellung von                       |
|              http://www.hackerboard.de/thread.php?threadid=25173
|---------------------------------------------------------|
| folgende Aufgabenstellung:                              |
|   Dabei soll der User wählen, welchen Test er möchte:   |
|    1. Brute Force. Überprüfen ob die Zahl durch eine    |
|       Zahl zwischen 2 und xxx Teilbar ist (Schleife).   |
|       Optimiere diese Schleife bestmöglich.             |
|    2. Der kleine Satz von Fermat                        |
|    3. Miller-Raben-Test                                 |
|---------------------------------------------------------|
| fileinfo: prim_func.cpp - functions to get prim         |
|--------------------------------------------------------*/

#include "head.h"


//--------------------------------------------------------------//
//                   |function DoBruteForce |                   //
//                   -----------------------                    //
// description:                                                 //
//    DoBruteForce versucht mit einer gegebenen Anzahl an       //
//    Versuchen durch die gegebene Zahl zu teilen. Ist eine     //
//    Zahl dabei, die Teilbar ist durch die gegebene und sie ist//
//    ungleich dieser, dann ergibt sich daraus, dass es keine   //
//    Primzahl ist.                                             //
// used for:                                                    //
//    Um mit Gewalt eine vermeintliche Primzahl zu testen.      //
//                        --------------------------------------//
// Input:     ulVersuche    wieviele Durchgänge gemacht werden  //
//                        --------------------------------------//
//            ulZahl        die zu testende Zahl.               //
//                        --------------------------------------//
// Output:   returns false wenn geteilt wurden konnte.          //
//--------------------------------------------------------------//
bool DoBruteForce(unsigned long ulVersuche, unsigned long ulZahl)
{
    unsigned long ulTeiler  = 2; // auf 3 setzen, da bis 2 alles zu klein
    ulVersuche              = ulVersuche + 2;

    while(ulTeiler < ulZahl && ulTeiler < ulVersuche)
    {
        if(ulZahl%ulTeiler == 0)    // ohne Rest teilbar
            return false;           // keine Primzahl
        
        ulTeiler++;
    }

    return true;
}

//--------------------------------------------------------//
//                  | function DoFermat |                 //
//                  ---------------------                 //
// description:                                           //
//    Fermat besagt, dass eine Zahl p, bei der gilt: a    //
//    hoch (p - 1) mod p = 1, eine (Pseudo)Primzahl ist.  //
//    Die Funktion testet die gegebene Zahl darauf.       //
// used for:                                              //
//    Um mit Fermat eine Pseudo-Primzahl festzustellen.   //
//                            ----------------------------//
// Input: ulZahl              die zu testende Zahl        //
//                            ----------------------------//
//                            ----------------------------//
// Output: bool               true wenn prim              //
//                            ----------------------------//
//--------------------------------------------------------//

bool DoFermat(unsigned long ulZahl)
{
    unsigned long a = 2;                  // a muss 0<a<ulZahl sein.
    if((unsigned long)pow(a,ulZahl-1)%ulZahl == 1) // der kleine Fermat besagt: "a^(p-1) mod p = 1
        return true;
    else
        return false;
}

//--------------------------------------------------------//
//                 | function DoMiller |                  //
//                 ---------------------                  //
// description:                                           //
//    Die Miller-Rabin Methode basiert auf dem kleinen    //
//    Satz von Fermat. Eine Zahl p muss zwei              //
//    Eigenschaften erfuellen, dann gilt sie mit 3:4      //
//    Chance als Primzahl.                                //
// used for:                                              //
//    Um eine Zahl mit der Miller-Rabin Methode auf prim  //
//    zu testen.                                          //
//                            ----------------------------//
// Input: ulZahl              zu testende Zahl            //
//                            ----------------------------//
//                            ----------------------------//
// Output: bool               true wenn Eigenschaften     //
//                            erfuellt.                   //
//                            ----------------------------//
//--------------------------------------------------------//

bool DoMiller(unsigned long ulZahl)
{
 
    // shack the devil:
    srand( (unsigned)time( NULL ) );

    unsigned long ulBasis;      
    unsigned long ulUngerade;   // eine Zahl, geteilt durch 2 != Rest 0
    unsigned int  uiStellen;    // Stellenanzahl + 1 von ulZahl

    
   /* ulBasis = (ulZahl-1) * rand() / (RAND_MAX + 1.0);
    if(ulBasis%2 == 0)
        ulBasis--;*/
    ulBasis = 2;

    ulUngerade = 42 * rand()/ (RAND_MAX + 3.0);
    if(ulUngerade%2 == 0)
        ulUngerade--;

    uiStellen = 1;
    unsigned long ulBuffer = ulZahl;
    while(ulBuffer > 0)
    {
        ulBuffer = ulBuffer/10;
        uiStellen++;
    }
    
    // ulBasis und ulZahl müssen teilerfremd sein. => ggT == 1
    if(ggT(ulZahl, ulBasis) != 1)
        return false;



    bool bTest1 = false;
    bool bTest2 = false;

    // Teste Zahlen durch:
    // Test 1:
    if((unsigned long)pow(ulBasis, ulUngerade)%ulZahl != 1)
        bTest1 = true;

    // Test 2:
    for(unsigned int t = 0; t < uiStellen; t++)
    {
        unsigned long ulPow = pow(2, t);
        ulPow = ulPow * ulUngerade;
        if((long)pow(ulBasis, ulPow)%ulZahl != -1)
            bTest2 = true;
        else
            bTest2 = false;
    }

    if(bTest1 && bTest2)
        return true;
    else
        return false;


}

//--------------------------------------------------------//
//                  |function ggT |                       //
//                  ---------------                       //
// description:                                           //
//    Sucht den groessten gemeinsamen Teiler zweier       //
//    gegebener Zahlen.                                   //
// used for:                                              //
//    um den ggT zweier Zahlen zu bestimmen.              //
//                            ----------------------------//
// Input: m, n                Zahlen aus denen der ggT    //
//                            ermittelt werden soll.      //
//                            ----------------------------//
//                            ----------------------------//
// Output: unsigned long      gibt den ggT der beiden aus.//
//                            ----------------------------//
//--------------------------------------------------------//

unsigned long ggT(unsigned long m, unsigned long n)
{
  unsigned long iBuffer;
  while (n > 0)
  {
    iBuffer = n;
    n = m%n;        // Rest aus m/n
    m = iBuffer;    // m = altes n
  }
  return m;
}

head.h:

Code:

/*--------------------------------------------------------|
| primzahlen - Aufgabenstellung von                       |
|              http://www.hackerboard.de/thread.php?threadid=25173
|---------------------------------------------------------|
| folgende Aufgabenstellung:                              |
|   Dabei soll der User wählen, welchen Test er möchte:   |
|    1. Brute Force. Überprüfen ob die Zahl durch eine    |
|       Zahl zwischen 2 und xxx Teilbar ist (Schleife).   |
|       Optimiere diese Schleife bestmöglich.             |
|    2. Der kleine Satz von Fermat                        |
|    3. Miller-Raben-Test                                 |
|---------------------------------------------------------|
| fileinfo: head.h - main header                          |
|--------------------------------------------------------*/



// -------- INCLUDES ---------- //
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>


// -------- PROTOTYPES ------- //
bool DoBruteForce(unsigned long, unsigned long);
bool DoFermat(unsigned long);
bool DoMiller(unsigned long);

unsigned long ggT(unsigned long, unsigned long);

// -------- ELSE ---------- //
using namespace std;

PS: Das ganze ist als .zip auch noch im Anhang.

PSS: Ich hoffe mein erster Beitrag ist nicht zu lang

Anzeige

- Anzeige -

mig · 17.08.06, 22:53

so Aufgabe war im endeffekt doch umfangreicher wie gedacht

hier erst mal meine Java-Variante:

Code:

import Prog1Tools.IOTools;
import java.lang.Math;
import java.util.Random;
import java.math.BigInteger;

class Primzahl {
	Random ran = new Random();
	BigInteger zero = BigInteger.ZERO;
	BigInteger one = BigInteger.ONE;
	
	
	public static void main(String[] args) {
		Primzahl prim = new Primzahl();
		boolean a = true;
		System.out.println("Bruto Force             (1)");
		System.out.println("Fermat                  (2)");
		System.out.println("Miller                  (3)");
		System.out.println("Euler                   (4)");
		System.out.println("Giuga                   (5)");
		System.out.println("Wilson                  (6)");
		System.out.println("Primfaktorzerlegung     (7)");
		System.out.println("Abbrechen               (8)");
		while(a) {
			System.out.print("\nWaehle Algorithmus : ");
			int zahl = IOTools.readInteger();
			switch (zahl) {
				case 1: prim.bruto()	; break;
				case 2: prim.fermat()	; break;
				case 3: prim.miller()	; break;
				case 4: prim.euler()	; break;
				case 5: prim.giuga()	; break;
				case 6: prim.wilson()	; break;
				case 7: prim.zerlegung(); break;
				case 8: a=false			; break;
				default: System.out.println("Falsche Eingabe!");
			}
		}
		
	}
	
	/* 
	** Brute Force
	**
	** es wird für 2 < i < eingabe
	** versucht einen teiler für eingabe zu finden
	** wenn dem so ist, ist eingabe keine Primzahl
	*/
	public void bruto() {
		System.out.print("Eingabe: ");
		BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
		boolean test = true;
		
		for(int i = 2; i < eingabe.intValue(); i++)
			if(eingabe.mod(BigInteger.valueOf(i)).compareTo(zero)==0)
				test = false;
		
		if(test)
			System.out.println(eingabe +" ist Primzahl");
		else {
			System.out.println(eingabe +" ist keine Primzahl");
			zerlegung(eingabe.intValue());
		}
	}
	
	
	/* 
	** Der kleine Satz von Fermat 
	** 
	** Für jede ganze Zahl a, die nicht durch p teilbar ist gilt:
	** a^(p-1) mod p = 1 mod p   <=> a^p mod p = a mod p
	** a: zufällig gewählt mit 0 < a < eingabe
	** 
	** Durch umformen : a^p mod p = a
	*/
	

	public void fermat() {
		System.out.print("Eingabe: ");
		BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
		boolean teiler = true;
		BigInteger a = BigInteger.valueOf(0);
		while(teiler) {
			a = new BigInteger(eingabe.bitLength(),ran);  //Zufallszahl
			a.add(one);
			if(ggT(a,eingabe).compareTo(one) == 0)
				teiler=false;
		}

		if(a.modPow(eingabe,eingabe).compareTo(a) == 0)
			System.out.println(eingabe +" ist Primzahl");
		else {
			System.out.println(eingabe +" ist keine Primzahl");
			zerlegung(eingabe.intValue());
		}
	}
	
	
	
	/* 
	** Miller-Rabin-Test
	** 
	** Es gilt: a^d mod n = 1 mod n    oder   a^(d*2^r) mod n = -1 mod n
	** mit (n-1) = d*2^s
	** a: zufällig gewählt mit 1 < a < n 
	** s: größte Zahl die (n-1) mit 2^r teilt       (n-1)/(2^r)
	** d: ist dann das ergebnis von (n-1)/(2^r) muss ebenfalls ? N sein
	** 
	** Durch umformen : (a^d -1) mod n = 0   oder (a^(d*2^r)+1) mod n = 0
	** 
	** r wird hier getestet mit: 0 < r < (s-1)
	*/
	
	public void miller() {
		System.out.print("Eingabe: ");
		BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
		System.out.print("Zeugen: ");
		BigInteger zeugen = BigInteger.valueOf(IOTools.readInteger());
		boolean test = false;
		BigInteger two = BigInteger.valueOf(2);
		
		
		for(int z=0; z < zeugen.intValue(); z++) {
			BigInteger s = zero;
			BigInteger basis = new BigInteger(eingabe.bitLength()-1,ran);  //Zufallszahl
			
			for(int i=1; eingabe.subtract(one).intValue() < Math.pow(2,i);i++) {
				if(eingabe.subtract(one).mod(BigInteger.valueOf((long)Math.pow(2,i))).compareTo(zero)==0)
					s=BigInteger.valueOf(i);
			}
			
			BigInteger d = eingabe.subtract(one).divide(BigInteger.valueOf((long)Math.pow(2,s.intValue())));
			
			if(basis.modPow(d,eingabe).subtract(one).compareTo(zero) == 0)
				test = true;

			for(int r = 0;r <= s.subtract(one).intValue();r++)
				if( basis.pow(d.multiply(two.pow(r)).intValue()).add(one).mod(eingabe).compareTo(zero)== 0)
					test = true;
		}
		
		if(test)
			System.out.println(eingabe +" ist Primzahl");
		else {
			System.out.println(eingabe+" ist keine Primzahl");
			zerlegung(eingabe.intValue());
		}
	}
	
	/*
	** Euler und das Legendre-Symbol
	**
	** Für jede ungerade Primzahl p und jede ganze Zahl a, 
	** die nicht durch p teilbar ist, gilt:
	** a^((p-1)/2) mod p = 1 mod p        oder    a^((p-1)/2) mod p = -1 mod p
	**
	** Durch umformen : (a^((p-1)/2)-1) mod p = 0  oder  (a^((p-1)/2)+1) mod p = 0
	*/
	
	
	public void euler() {
		System.out.print("Eingabe: ");
		BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
		BigInteger two = BigInteger.valueOf(2);
		BigInteger a = new BigInteger(eingabe.bitLength()-1,ran);  //Zufallszahl
		a = a.modPow((eingabe.subtract(one)).divide(two),eingabe);

		if(a.compareTo(one) == 0)
			System.out.println(eingabe + " ist Primzahl");
		else if(a.compareTo(eingabe.subtract(one)) == 0)
			System.out.println(eingabe + " ist Primzahl");
		else {
			System.out.println(eingabe + " ist keine Primzahl");
			zerlegung(eingabe.intValue());
		}
	}
	
	/*
	** Giuga
	**
	** Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl p gilt:
	** 1^(p-1)+2^(p-1)+ ... +(p-1)^(p-1) mod p = -1 mod p
	**
	** Durch umformen : (1^(p-1)+2^(p-1)+ ... +(p-1)^(p-1) + 1) mod p = 0
	*/
	public void giuga() {
		System.out.print("Eingabe: ");
		BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
		BigInteger erg = BigInteger.valueOf(0);
		
		for(int i = 1;i < eingabe.intValue();i++){
			erg = erg.add(BigInteger.valueOf(i).pow(eingabe.subtract(one).intValue()));
		}
		
		if(erg.add(one).mod(eingabe).compareTo(zero)==0)
			System.out.println(eingabe +" ist Primzahl");
		else {
			System.out.println(eingabe +" ist keine Primzahl");	
			zerlegung(eingabe.intValue());
		}
	}
	
	/*
	** Wilson
	** Er besagt: Genau dann ist p > 1 eine Primzahl, wenn
	** (p-1)! mod p = -1 mod p
	**
	** Durch umformen : ((p-1)! + 1) mod p = 0
	*/
	public void wilson() {
		System.out.print("Eingabe: ");
		BigInteger eingabe = BigInteger.valueOf(IOTools.readInteger());
		BigInteger f = fak(eingabe.subtract(one));
		if(f.add(one).mod(eingabe).compareTo(zero)==0)
			System.out.println(eingabe +" ist Primzahl");
		else {
			System.out.println(eingabe +" ist keine Primzahl");
			zerlegung(eingabe.intValue());
		}
	}
	
	
	// Fakultät 
	public BigInteger fak(BigInteger i) {
		if(i.compareTo(zero)==0 || i.compareTo(one)==0)
			return one;
		else return i.multiply(fak(i.subtract(one)));
	}
	
	// ggT
    public BigInteger ggT(BigInteger n, BigInteger m) {
    	if( n.compareTo(zero) == 0 || m.compareTo(zero) == 0)
    		return zero;
    	else {
    		while(n.compareTo(m) != 0) {
    			if(n.compareTo(m) == 1)
    				n = n.subtract(m);
    			else
    				m = m.subtract(n);
    		}
    		return n;
    	}
    }
    
    /*
    ** Primfaktorzerlegung
    **
    ** via Sieb des Eratosthenes alle Primzahlen bis n herrausfinden
    ** und dannach mit der größten beginnend durch n teilen
    ** und somit die Primfaktoren ausfindig machen falls vorhanden
    */
    
    public void zerlegung() {
    	System.out.print("Zahl: ");
		int n = IOTools.readInteger();
		String exp = "";
		boolean gestrichen [] = new boolean[n];
		boolean einmal = false;
		int prim = 2;
		
		for(int i =2 ; i<n; i++)
			gestrichen[i] = false;

		while((prim*prim) <= n) {
			if(gestrichen[prim] == false)
				for (int j = 2; prim*j<n;j++)
					gestrichen[prim*j] = true;
			prim = prim +1;	
		}

		for(int i = (n-1); i>1 ; i--) {
			if(gestrichen[i] == false) {
				boolean j = true;
				int zahl=0;
				while(j) {
					if(n%i == 0){
						zahl++;
						n = n/i;
						einmal = true;
					}
					else
						j = false;
				}
				if(zahl != 0)
					exp = exp + i + "^" + zahl + " * ";
			}
		}
		if(einmal) {
			exp = exp.substring(0, exp.length() - 2);
			System.out.println(exp);
		}
		else 
			System.out.println("Es gibt keine Primfaktorzerlegung ");	
	}
	
	// Nochmal für die nicht Primzahlen wird automatisch aufgerufen
	
	public void zerlegung(int n) {
		String exp = "";
		boolean gestrichen [] = new boolean[n];
		boolean einmal = false;
		int prim = 2;
		
		for(int i =2 ; i<n; i++)
			gestrichen[i] = false;

		while((prim*prim) <= n) {
			if(gestrichen[prim] == false)
				for (int j = 2; prim*j<n;j++)
					gestrichen[prim*j] = true;
			prim = prim +1;	
		}

		for(int i = (n-1); i>1 ; i--) {
			if(gestrichen[i] == false) {
				boolean j = true;
				int zahl=0;
				while(j) {
					if(n%i == 0){
						zahl++;
						n = n/i;
						einmal = true;
					}
					else
						j = false;
				}
				if(zahl != 0)
					exp = exp + i + "^" + zahl + " * ";
			}
		}
		if(einmal) {
			exp = exp.substring(0, exp.length() - 2);
			System.out.println(exp);
		}
		else 
			System.out.println("Es gibt keine Primfaktorzerlegung ");	
	}		
}

zum Programm an sich ... es sind mehrere Varianten eine Primzahl zu testen.
Gibt allerdings, bei ein paar Verfahren, noch Probleme wenn man kleine Zahlen wählt.
Die Zeugen kann man nur beim Miller-Verfahren wählen.
Das mit ggT hab ich nur beim Satz von Fermat gemacht... da funkionierts aber noch net so wie es sein sollte, Verbesserungsvorschläge?
Die Methode zum Faktorisieren ist 2 mal drin da sie einmal wie verlangt automatisch aufgerufen wird wenn eine Zahl als nicht Prim deklariert wird und nochmal falls man selber
ein Zahlenpaar testen möchte.

Feedback ist natürlich sehr erwünscht !!!

mfg mig

amkoroew · 25.01.07, 17:25

Hoe
Hab mal en Programm geschrieben des die Primfaktoren einer eingegebenen Zahl ausgibt.

Die Berechnung Funktioniert wie folgt:
X=eingegebene Zahl
man prüft 2 - sqrt(X)
da ausser der eigenen Zahl kein Primfaktor größer sein kann als die 2. Wurzel der Zahl.
Ich hoff des ist einigermaßen verständlich.
Der Rest mit dem teilen gleiche Zahl erneut probieren usw sollte klar sein.

hier mein Code:

Und hier noch die exe:

**Elderan** · 25.01.07, 20:57

Hallo,
@amkoreow:
Deinen Code kann man noch verbessern und verkürzen:

Code:

//PseudoCode in C Syntax

FaktorZerlegung(int x):
   int i=0;
   while (x > 1)
   {            
      if( (x % Primnumber(i)) ) == 0)
      {
           //x ist ein Primfaktor, Ausgabe von x

            x /= Primnumber(i);
        }
       else
          i++;
   }


//==========

//Gibt die Primzahl an der i. Stelle, also bei 0 die 2, bei i=1 die 3 usw.
//primnumbers muss mindestens die Primzahlen 2 und 3 enthalten.
Primnumber(int i):  
   if( i < count(primnumbers))
     return primnumbers[i];
  else
  {  
  for(int k = primnumbers[count(primnumbers)-1]; ; i+=2)
      if(IsPrime(k))
      {
         AddNumberToArray(k); //Fügt k dem primnumbers Array hinzu
         return k;
      }
  }

Dieser Code dürfte schneller laufen, denn er hat einen Vorteil:
Er überprüft nur, ob eine Zahl auch wirklich durch eine Primzahl teilbar ist. Du testest z.B. auch, ob die Zahl auch durch z.B. 4 oder 6 oder 9 teilbar ist.

Die Funktion Primnumber(int i) gibt die Primzahl an der jeweiligen Stellen aus. Dies hat den Vorteil, dass man bei vielen Primfaktoren-Zerlegungen die Primzahlen in einem Array abspeichern kann und immer wenn eine neue Primzahl gefunden wurde, wird diese dem Array hinzugefügt.

Man generiert z.B. per Sieb des Eratosthenes, die ersten 100k Primzahlen (Dauer: 0,00x Sekunden) und speichert die in primnumbers ab, ob man speichert fest die ersten 1000 Primzahlen im Code.

Bei vielen Primfaktorenzerlegungen kann man so sehr viel Zeit einsparen.

amkoroew · 28.01.07, 16:31

Hi Elderan
Danke für den Tipp!!
Hab davor no nie was von dem Sieb gehört ghabt^^

Stein · 30.03.07, 21:04

PHP-Code:

  <?php
/*Das Sieb des Eratosthenes:
"Man muss nicht rechnen können um Primzahlen zufinden nur zählen." Normaler Weise schreibt man alle Zahlen auf ein Blatt und fängt bei 2 an:
 2 wir nicht durchgestrichen, zwei weiter (4) wird durch gestrichen usw. dann mit 3.*/

$zahlen = array(0);//Beginn der Berechnung
for ($i=1;$i<100000;$i++){
    $zahlen[$i] =1;//erzeugt ein Array mit den werten 1-30000 und 1(=true)
}
for($j=2;2*$j<100000;$j++){//"siebt" alle Zahlen bis zu Hälfte
    if ($zahlen[$j] == 1){//nur Vielfach von Primzahlen werden druchgestrichen wenn 
        for($k=$j;$k<100000;){ //ich alle Vielfach von 2 habe brauche ich die von 4 nicht.
            $k=$k+$j;
            $zahlen[$k] = 0;//Vielfach sind keine Primzahlen
        }
    }        
}    //Ende der Berechnung
//Beginn der Ausgabe
for($l=1;$l<100000;$l++){
    if($zahlen[$l]==1){
        echo $l."<br>";
    }
}
?>

Das Problem bei dieser Berechnung von Primzahlen ist, dass man eine Menge Ramspeicher(10000 schaft mein PC) braucht. Aber das kann man ja bei PHP gut mit einer Datenbank umgehen und dann ist die Methode meiner Ansicht nach auch sehr gut zum finden von Primzahlen. Zum festellen ob x prim ist, ist diese Methode eher ungeeignet. Was haltet ihr davon? Ich hatte das Ding auch mal in C++ geschrieben und habe da 30000 geschaft. Wenn Intresse ist bau ich das ganze noch mal so das in eine Datenbank geht und dass man dann auch einwenig weiter kommt. Erst mal ich das ganze um eine Primzahlpaarfunktion.

Indi · 31.03.07, 08:54

Zitat:

Das Problem bei dieser Berechnung von Primzahlen ist, dass man eine Menge Ramspeicher(10000 schaft mein PC) braucht.

Du kannst einiges dabei einsparen, wenn du die Zahlen, die schon auf den ersten Blick nicht Prim sein können, gar nicht erst in dein Array pushst.

Im folgenden:
- alle geraden Zahlen
- alle Vielfachen von fünf; dh. mit den Ziffern 0 oder 5 am Schluss
- alle Zahlen deren Quersumme durch 3 teilbar ist.

Angenommen du untersuchst den Zahlen-Bereich 31 bis 60:
Grundmenge: 30 Zahlen
streichst du die geraden bleiben: 15 Zahlen
streichst du durch 5 teilbar bleiben: 12 Zahlen
streichst du durch 3 teilbar bleiben: 8 Zahlen

8 von 30, das ist eine Reduktion von 73,33 % und ist in jedem Zahlenbereich anwendbar.

Stein · 31.03.07, 10:14

Zwischen 30 & 60 hast du 73,33 aber je Mehr Primzahlen unterhalb des Bereiches exestieren, desto ungenauer wird das ganze. Trotzdem ist interessant das ganze mal für eine bestimment Bereich anzuwenden.

Indi · 31.03.07, 13:22

Inwiefern wird das ungenauer?

Nachtrag:
Ich meinte nicht, dass du nur einen bestimmten Bereich untersuchst. Es ging darum, dass in einem Bereich mit dem Startwert x*30+1 und einem Endwert (x+1)*30, 73,33% der Zahlen in diesem Bereich nicht Prim sein können. Die Reihenfolge der Zahlen die noch zu untersuchen bleiben sind dabei immer gleich. Nur sollte man dabei immer von einem Wert x*30 ausgehen, weil sich die durch 3 teilbaren Zahlen immer verschieben, bis du bei (x+1)*31 wieder bei der ursprünglichen Ausgangsstellung angelangt bist...

Wenn du daher unter Anbetracht der sonstigen oben genannten Merkmale anstatt den Zähler einfach zu inkrementieren, diese Reihenfolge anwendest, wird das ~ 73 % Speicher und gegebenfalls Rechenleistung sparen...

my2$/100 · 09.04.07, 17:28

Zitat:

Original von Stein
Das Problem bei dieser Berechnung von Primzahlen ist, dass man eine Menge Ramspeicher(10000 schaft mein PC) braucht.

Da ich nicht glaube, das dein PC nur 64 kB Hauptspeicher hat, denke ich, das Du einen extrem ineffizienten Algorithmus geschrieben hast. Eigentlich sollte dein Array nicht mehr als 40 kB Speicher zur Laufzeit belegen. (10000 Einträge * 4 Bytes / 1024=39,06 - bzw. etwas in dieser Größenordnung)

Ich mutmaße mal, dass deine erste for-Schleife bei (fast) jedem Durchlauf Speicher reserviert um das Array zu vergrößern. Ebenso müssen bei jedem Durchlauf alle Elemente umkopiert werden. Der Speicher wird aber nicht sofort wieder freigegeben, sondern erst wenn der Garbage Collector anspringt. Das alles sollte sich leicht umgehen lassen: $zahl = array(30000);

Ich habe es in C++ probiert: Array mit 100Mio Einträgen (Typ: char, Soll-Größe: 96MB). Der Speicherverbrauch ging zur Laufzeit wie erwartet um etwa 100MB nach oben. Die Laufzeit betrug 49 Sekunden auf einen P3 - 1,1GHz (ohne Ausgabe).

**Elderan** · 09.04.07, 17:47

Hallo,
@my2$: Leider kann man in PHP kein Array mit einer bestimmten Anzahl an Elementen erstellen sondern die Größe wird dynamisch festgelegt/vergrößert, was leider sehr zur Lasten der Perfomance geht.

Ein:
$zahl = array(30000);

Würde bewirken, dass du ein Array mit 1 Element bekommst, wobei das 1. Element den Wert 30000 hat.

**bitmuncher** · 09.04.07, 18:31

Zitat:

Original von Elderan
Hallo,
@my2$: Leider kann man in PHP kein Array mit einer bestimmten Anzahl an Elementen erstellen ...

Code:

for($i=0; $i<=30000; $i++) {
  meinarray[$i] = '';
}

Wzbw.

my2$/100 · 10.04.07, 00:48

Zitat:

Original von Elderan
Ein:
$zahl = array(30000);

Würde bewirken, dass du ein Array mit 1 Element bekommst, wobei das 1. Element den Wert 30000 hat.

Man lernt nie aus - kenne PHP nur rudimentär. Also Sorry Stein, ich war etwas voreilig

.

Ich habe ein Versuch gemacht, ob das evtl. effizienter geht:

Code:

$a = array(0);
for($i=0; $i<1000000; i$) {
   $a[$i] = $i;
}

Speicherverbrauch: 74MB - Laufzeit: 2.56 Sek

Code:

$a = range(1,1000000);

Speicherverbrauch: 74MB - Laufzeit: 1.78 Sek

**Elderan** · 11.04.07, 19:30

Hallo,
@bitmuncher: Dies ist leider nicht richtig.
Zuerst wird ein Array erstellt mit 0 Elementen.
Beim 1. Schleifendurchlauf wird die Größe des Arrays um 1 vergrößert auf insgesamt 1 Element. Beim 2. Durchlauf wird die Größe erneut vergrößert auf insgesamt 2 Elemente.
Beim nächsten Durchlauf dann wieder um 1 vergrößert auf 3 Elemente und so weiter.

Das Problem dabei ist, dass PHP immer wieder neu Speicher reservieren muss sowie das alte Array an den neuen Speicher verschieben muss.
Bei deinem Schleifendurchlauf würde also 30000 mal neuer Speicher reserviert, und das Array würde 30000 mal verschoben werden, was sehr Zeitintensiv ist.

Eine Möglichkeit wie in C gibt es (afaik) nicht:
in C: int[30000] array;

Dies würde Speicher für 30k Elemente reservieren.

Deine Schleife (bzw. PHP) würde 30000 mal die Funktion realloc() aufrufen, um den Speicher der Variable zu vergrößern, was natürlich vollkommen unnötiger Rechenaufwand ist.

Aber es kommt noch schlimmer: Bevor neuer Speicher reserviert wird, muss PHP vorher überprüfen, ob ein Element mit dem Index $i vorhanden ist, welches es dann überschreiben würde.
Da dies nicht so ist, wird der Speicherbereich für das Array um 1 vergrößert.

Anzeige

- Anzeige -

05.05.06, 22:11	#1 (permalink)
Elderan Moderator Registriert seit: 30.03.04 Likes: 14	Primzahlen mit versch. Tests Anzeige Hallo, es soll ein Programm geschrieben werden, welches überprüft, ob eine Zahl eine Primzahlen ist. Dabei soll der User wählen, welchen Test er möchte: 1. Brute Force. Überprüfen ob die Zahl durch eine Zahl zwischen 2 und xxx Teilbar ist (Schleife). Optimiere diese Schleife bestmöglich. 2. Der kleine Satz von Fermat 3. Miller-Raben-Test 4. Ggf. noch andere Algorithmen Zusatz #1: Überprüfe, wie viele "falsche Primzahlen" die anderen Algorithmen zwischen 2 und xxxx (abhänig vom User) findet und gebe diese aus. Zusatz #2: Der User kann bei den Algorithmen bestimmen, wie viele "Zeugen" es geben soll. Zeuge bedeutet, wie oft die Zahl mit verschiedenen Basen getestet wurde (erhöht die Sicherheit der Aussage). Zusatz #3: Gebe von einer nicht Primzahl die Primfaktoren aus, am besten in einer exponentiellen Schreibweise. Also 200: 2^3 * 5^2 Links: Allg. Infos Primzahlen Primzahlen 2 bis 100 000

30.03.07, 21:04	#7 (permalink)
Stein Registriert seit: 10.10.05 Likes: 0	PHP-Code: <?php /Das Sieb des Eratosthenes: "Man muss nicht rechnen können um Primzahlen zufinden nur zählen." Normaler Weise schreibt man alle Zahlen auf ein Blatt und fängt bei 2 an: 2 wir nicht durchgestrichen, zwei weiter (4) wird durch gestrichen usw. dann mit 3./ $zahlen = array(0);//Beginn der Berechnung for ($i=1;$i<100000;$i++){ $zahlen[$i] =1;//erzeugt ein Array mit den werten 1-30000 und 1(=true) } for($j=2;2*$j<100000;$j++){//"siebt" alle Zahlen bis zu Hälfte if ($zahlen[$j] == 1){//nur Vielfach von Primzahlen werden druchgestrichen wenn for($k=$j;$k<100000;){ //ich alle Vielfach von 2 habe brauche ich die von 4 nicht. $k=$k+$j; $zahlen[$k] = 0;//Vielfach sind keine Primzahlen } } } //Ende der Berechnung //Beginn der Ausgabe for($l=1;$l<100000;$l++){ if($zahlen[$l]==1){ echo $l."<br>"; } } ?> Das Problem bei dieser Berechnung von Primzahlen ist, dass man eine Menge Ramspeicher(10000 schaft mein PC) braucht. Aber das kann man ja bei PHP gut mit einer Datenbank umgehen und dann ist die Methode meiner Ansicht nach auch sehr gut zum finden von Primzahlen. Zum festellen ob x prim ist, ist diese Methode eher ungeeignet. Was haltet ihr davon? Ich hatte das Ding auch mal in C++ geschrieben und habe da 30000 geschaft. Wenn Intresse ist bau ich das ganze noch mal so das in eine Datenbank geht und dass man dann auch einwenig weiter kommt. Erst mal ich das ganze um eine Primzahlpaarfunktion. __________________ Steinhagelvoll

31.03.07, 10:14	#9 (permalink)
Stein Registriert seit: 10.10.05 Likes: 0	Zwischen 30 & 60 hast du 73,33 aber je Mehr Primzahlen unterhalb des Bereiches exestieren, desto ungenauer wird das ganze. Trotzdem ist interessant das ganze mal für eine bestimment Bereich anzuwenden. __________________ Steinhagelvoll

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Primzahlen	T1G3R	Cryptography & Encryption	3	31.10.08 13:08
[c++] Primzahlengenerator: Ganzzahlige primzahlen	_fux_	Code Kitchen	15	17.09.08 21:47
Script für automatische Tests erstellen??	ecologys	Code Kitchen	0	29.06.04 13:46
2 versch. versionen von md5?	immado	Cryptography & Encryption	5	18.04.04 17:06
Tests von Testreich.com	kressi	Umfragen	12	18.12.03 15:42

25.01.07, 20:57	#5 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, @amkoreow: Deinen Code kann man noch verbessern und verkürzen: Code: //PseudoCode in C Syntax FaktorZerlegung(int x): int i=0; while (x > 1) { if( (x % Primnumber(i)) ) == 0) { //x ist ein Primfaktor, Ausgabe von x x /= Primnumber(i); } else i++; } //========== //Gibt die Primzahl an der i. Stelle, also bei 0 die 2, bei i=1 die 3 usw. //primnumbers muss mindestens die Primzahlen 2 und 3 enthalten. Primnumber(int i): if( i < count(primnumbers)) return primnumbers[i]; else { for(int k = primnumbers[count(primnumbers)-1]; ; i+=2) if(IsPrime(k)) { AddNumberToArray(k); //Fügt k dem primnumbers Array hinzu return k; } } Dieser Code dürfte schneller laufen, denn er hat einen Vorteil: Er überprüft nur, ob eine Zahl auch wirklich durch eine Primzahl teilbar ist. Du testest z.B. auch, ob die Zahl auch durch z.B. 4 oder 6 oder 9 teilbar ist. Die Funktion Primnumber(int i) gibt die Primzahl an der jeweiligen Stellen aus. Dies hat den Vorteil, dass man bei vielen Primfaktoren-Zerlegungen die Primzahlen in einem Array abspeichern kann und immer wenn eine neue Primzahl gefunden wurde, wird diese dem Array hinzugefügt. Man generiert z.B. per Sieb des Eratosthenes, die ersten 100k Primzahlen (Dauer: 0,00x Sekunden) und speichert die in primnumbers ab, ob man speichert fest die ersten 1000 Primzahlen im Code. Bei vielen Primfaktorenzerlegungen kann man so sehr viel Zeit einsparen.

28.01.07, 16:31	#6 (permalink)
amkoroew Registriert seit: 18.01.07 Likes: 0	Hi Elderan Danke für den Tipp!! Hab davor no nie was von dem Sieb gehört ghabt^^

31.03.07, 13:22	#10 (permalink)
Indi Member of Honour Registriert seit: 02.10.01 Likes: 0	Inwiefern wird das ungenauer? Nachtrag: Ich meinte nicht, dass du nur einen bestimmten Bereich untersuchst. Es ging darum, dass in einem Bereich mit dem Startwert x30+1 und einem Endwert (x+1)30, 73,33% der Zahlen in diesem Bereich nicht Prim sein können. Die Reihenfolge der Zahlen die noch zu untersuchen bleiben sind dabei immer gleich. Nur sollte man dabei immer von einem Wert x30 ausgehen, weil sich die durch 3 teilbaren Zahlen immer verschieben, bis du bei (x+1)31 wieder bei der ursprünglichen Ausgangsstellung angelangt bist... Wenn du daher unter Anbetracht der sonstigen oben genannten Merkmale anstatt den Zähler einfach zu inkrementieren, diese Reihenfolge anwendest, wird das ~ 73 % Speicher und gegebenfalls Rechenleistung sparen...

09.04.07, 17:47	#12 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, @my2$: Leider kann man in PHP kein Array mit einer bestimmten Anzahl an Elementen erstellen sondern die Größe wird dynamisch festgelegt/vergrößert, was leider sehr zur Lasten der Perfomance geht. Ein: $zahl = array(30000); Würde bewirken, dass du ein Array mit 1 Element bekommst, wobei das 1. Element den Wert 30000 hat.

11.04.07, 19:30	#15 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, @bitmuncher: Dies ist leider nicht richtig. Zuerst wird ein Array erstellt mit 0 Elementen. Beim 1. Schleifendurchlauf wird die Größe des Arrays um 1 vergrößert auf insgesamt 1 Element. Beim 2. Durchlauf wird die Größe erneut vergrößert auf insgesamt 2 Elemente. Beim nächsten Durchlauf dann wieder um 1 vergrößert auf 3 Elemente und so weiter. Das Problem dabei ist, dass PHP immer wieder neu Speicher reservieren muss sowie das alte Array an den neuen Speicher verschieben muss. Bei deinem Schleifendurchlauf würde also 30000 mal neuer Speicher reserviert, und das Array würde 30000 mal verschoben werden, was sehr Zeitintensiv ist. Eine Möglichkeit wie in C gibt es (afaik) nicht: in C: int[30000] array; Dies würde Speicher für 30k Elemente reservieren. Deine Schleife (bzw. PHP) würde 30000 mal die Funktion realloc() aufrufen, um den Speicher der Variable zu vergrößern, was natürlich vollkommen unnötiger Rechenaufwand ist. Aber es kommt noch schlimmer: Bevor neuer Speicher reserviert wird, muss PHP vorher überprüfen, ob ein Element mit dem Index $i vorhanden ist, welches es dann überschreiben würde. Da dies nicht so ist, wird der Speicherbereich für das Array um 1 vergrößert.

[HaBo]

Primzahlen mit versch. Tests