Primzahlenberechnung mit BASH

O

OSP-User

Eroberer
Hi,

ich bin gerade dabei (bzw. denke noch nach wie man das am besten realisiert) ein BASH Tool zu schreiben, dass eine Primezahle berechnet und dann auf richtigkeit überprüft. Soll so eine Art Prime95 werden.

Ist das überhaupt möglich? Ich denke eigentlich schon, da ich durch die berechnung nur eine extrem hohe CPU-Last erreichen will. Naja und wenn er dann die Zahl raus hat soll er sie überprüfen!

Dazu muss ich mit ziemlich großen Zahlen rechnen aber wie? Also wie mache ich das am besten?

Kann mir jemand helfen? THX
 
Hallo

sono schrieb:
Die Funktion zur Ermittlung ist dabei wohl weniger das Problem.
Das sollte ja Schulstoff sein. ;)

www.primzahlen.de bietet da genügend Material.

Interessant wird es erst, wenn es um effektive Suche geht.

Aber da du ja richtig Systemlast willst, ist die brutale Methode sicher geeignet.
Das zweite Problem stellt sich dann in der Größe des Wertebereiches. -> 32 Bit Architektur oder doch 64 Bit ?!

Ich bezweifle allerdings, dass du da an die Grenzen stößt, wenn du das über die bash machen willst.
Das dauert richtig lang im großen Wertebereich!!:oldman
Die bash ist dabei sehr uneffektiv.

Habe eben mal ein sehr unsauberes schnell erstelltes Script auf meiner relativ langsamen Kiste (933MHZ PIII)gestetet.
Dabei wird das Script mit dem Parameter der maximalen Zahl ( bis wohin gesucht wird) aufgerufen.
Fehlerprüfung ist nicht integriert

Das sehr dirty Script ohne Garantie:
Code:
[i]cat primzahl.sh[/i]
[b]
#!/bin/bash
MIN=3;
MAX=$1;
ret=1;
CN=1;
PRIMZAHL=2;
function test_prim () {
        tmax=$1;
        for I in $(seq 2 $(( $tmax -1)));
        do
        ret=$(( $tmax % $I));
        if [ $ret -eq 0 ]; then
        return $ret;
        fi
        done
        if [ $ret -eq 1 ]; 
        then
        PRIMZAHL=$tmax;
        fi
        return $ret;
        }

for Z in $(seq 3 $MAX); do
        test_prim $Z;
        if [ $Z -eq $PRIMZAHL ]; then
        CN=$(($CN + 1));
        fi
        done
        echo Anzahl der Primzahlen $CN;
        echo "höchste Primzahl von $MIN bis $MAX ist $PRIMZAHL";

Ganz simpel wird jede Zahl durch alle kleineren Zahlen via MOD auf 0 getestet( Im prinzip eine verschachtelte Schleife, wobei die innere Schleife eine Funktion übernimmt.)
Das ist natürlich sehr uneffektiv!

Aber mal die Werte für meine relativ langsame Kiste:

wolle@:/home/wolle/temp$time ./primzahl.sh 1000

Anzahl der Primzahlen 168
höchste Primzahl von 3 bis 1000 ist 997

real 0m15.444s
user 0m10.814s
sys 0m2.392s
wolle@Nietzsche$time ./primzahl.sh 4000

Anzahl der Primzahlen 550
höchste Primzahl von 3 bis 4000 ist 3989

real 3m38.809s
user 3m15.618s
sys 0m12.426s


Der Test sollte analog leicht nachvollziehbar zu scripten sein.

Gruß Wolfgang
 
Ich denke eigentlich schon, da ich durch die berechnung nur eine extrem hohe CPU-Last erreichen will.

Er will nur ! ein hohe CPU Last da ist es egal wie dreckig und sauber der Algorithmus ist.

Und dann kann er auch über google ohne Probleme nen xbeliebigen Algo suchen und in bash programmieren.

Es ging wohl nicht darum dass das Programm je zu einem Ende kommt sonder, dass es die CPU bei 100% hält und das bis zum Sankt Nimmerleinstag.

Dein Lösungsvorschlag war im Gegensatz zu meinem natürlich Vorbildlich, aber jetzt muss der Junge ja gar nichts mehr selbst machen.

Böse Welt :devil:

Gruß Sono
 
Leider muss ich dich enttäuschen sono, denn ich habs schon hinbekommen. Durch die ganze theorie bei primezahlen.de hab ich mir dann was zusammen gebastelt. :brav:
Allerdings musste ich mit bedauern feststellen, das ich bei meinem A64 gerade mal ne Systemlast von 64% bekommen hab.

Außerdem sollte er schon zum Ende kommen... das hatte ich wohl vergessen zu sagen... ich wollte ne Maske machen in die man den End-Wert reinschreiben kann. Also in etwa so wie Wolfgang_1 das gemacht hat stimmt das schon!

Trotzdem Danke an euch beide!!!! :))
 

Ähnliche Themen

Problem mit Apache2 + MySQL Server

Probleme mit FFmpeg / PHP/ 70 Load / iowait

Server-Monitoring mit RRDTool

Linux Systemadministration v. Jochen Hein

Zurück
Oben