Du bist nicht angemeldet.

Lieber Besucher, herzlich willkommen bei: DeveloperTalk. Falls dies dein erster Besuch auf dieser Seite ist, lies bitte die Hilfe durch. Dort wird dir die Bedienung dieser Seite näher erläutert. Darüber hinaus solltest du dich registrieren, um alle Funktionen dieser Seite nutzen zu können. Benutze das Registrierungsformular, um dich zu registrieren oder informiere dich ausführlich über den Registrierungsvorgang. Falls du dich bereits zu einem früheren Zeitpunkt registriert hast, kannst du dich hier anmelden.

cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

1

26.06.2011, 14:55

Primzahlen einfach Berechnen.

Hi leute,
da mir letzte Nacht langweilig war und ich nicht wusste, was ich Programmieren soll, habe ich mal ein kleines Programm geschrieben, mit dem man sämtliche Primzahlen von einem 2 bis zu einem Bestimmten Punkt berechnen kann. Die Berechnung geht erst ab 2, weil 0 und 1 keine Primzahlen sind.
Das ganze funktioniert nach dem prinzip des Sieb des Eratosthenes.
Das ganze wurde in Java geschrieben.

Hier der Quellcode für alle dies interessiert:

Java-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.*;
public class primzahl {
	public static String tmp;
	public static int i2;
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	try {
		System.out.println("Bitte geben sie die Maximale länge der zu berechnenden Zahlen ein.");
		tmp = br.readLine();
		} catch (IOException io) {
			System.out.println("Error beim einlesen der Tastatureingaben");
			}
			long time1 = System.currentTimeMillis();
			int max = 0;
			max = Integer.parseInt(tmp);
			boolean[] isPrim = new boolean[max + 1];
		// Initialierung des Arrays
		for (int i = 0; i <= max; i++)
		isPrim[i] = true;
		// 0 und 1 sind keine Primzahlen
	isPrim[0] = isPrim[1] = false;
	// alle Vielfachen von Ganzzahlen ausschließen,
	// die kleiner als die Quadratwurzel von max sind.
	int n = (int) Math.ceil(Math.sqrt(max));
	for (int i = 0; i <= n; i++)
	if (isPrim[i])
	for (int j = 2 * i; j <= max; j+=i)
	isPrim[j] =false;
	// Primzahlen ausgeben
	System.out.print("Primzahlen anzeigen von 0 bis " + max + ": ");
	for (i2 = 0; i2 <= max; i2++)
	if (isPrim[i2])
	System.out.print(" " + i2 + " ");
	System.out.println();

	long time2 = System.currentTimeMillis();

	long timeEnde = time2-time1;
	System.out.println("benötigte Zeit: " + timeEnde + " Milisekunden");
	}
}


lg
Cedi

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »cedi« (26.06.2011, 19:37) aus folgendem Grund: Änderung am Code


Johannes S.

Fortgeschrittener

Beiträge: 440

Registrierungsdatum: 24.06.2011

Wohnort: Lychen

Beruf: Beruf?, Schüler

Danksagungen: 71

  • Private Nachricht senden

2

26.06.2011, 14:58

Das erinnert mich daran, wie mal ein paar Gruppenmitglieder in svz um die Wette gecodet haben, wer den schnellsten Priemzahlenrechner schreibt XD
Signatur ?

cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

3

26.06.2011, 15:07

das müsste so ziemlich der schnellste sein. Der Algorythmus ist sau schnell

Simon

Profi

Beiträge: 726

Registrierungsdatum: 14.06.2011

Danksagungen: 210

  • Private Nachricht senden

4

26.06.2011, 15:16

hey,
hast du keine Einrückung benutzt?
Oder hat WBB die zerstört?

Alex

Fortgeschrittener

Beiträge: 371

Registrierungsdatum: 23.06.2011

Wohnort: /home/alex

Danksagungen: 117

  • Private Nachricht senden

5

26.06.2011, 16:08

Also ich bin mir relativ sicher dass das nicht zu den schnellsten Algorithmen gehört, um Primzahlen zu berechnen o.O
alexthinking.com - yet another computer weblog

Zitat

Chuck Norris knows the state of schroedinger's cat.

Johannes S.

Fortgeschrittener

Beiträge: 440

Registrierungsdatum: 24.06.2011

Wohnort: Lychen

Beruf: Beruf?, Schüler

Danksagungen: 71

  • Private Nachricht senden

6

26.06.2011, 16:15

Naja, die haben damals mit C++ gearbeiet und da ging es wirklich um jede gleinigkeit.. die kamen da in 2 Sekunden schon ziemlich weit XD
Signatur ?

cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

7

26.06.2011, 17:46

naja, ich hab wirklich keine Einrückung benutzt.
Der Grund ist, dass ich das letzte Nacht Programmiert habe und neben her noch fleißig am chatten war und dann keine IDE verwendet hat oder ein Editor der mir die Einrückung macht sondern ich hab mit nem Terminal Editor namens pico gearbeitet. Und der macht zwar Syntaxhilighting aber keine automatische einrückung. Ich habs dann gelassen...

cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

8

26.06.2011, 17:48

und naja,
der Algorythmus ist wirklich sehr schnell würde ich behaupten. Und vorallem die Fehlerquote liegt bei 0,00%. Also alle Zaheln die auch ausgespuckt werden sind zu 100% Primzahlen. Das Sieb des Eratosthenes ist wirklich genial.

So, habs jetzt mal geändert MIT einrückung :) wirklich viel besser siehts nicht aus...

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »cedi« (26.06.2011, 18:24)


Patrick

Profi

Beiträge: 694

Registrierungsdatum: 23.06.2011

Wohnort: Wuppertal

Danksagungen: 168

  • Private Nachricht senden

9

26.06.2011, 18:30

Rückst du bei for() und if() nicht ein? o.O
Ex ungue leonem.

War der Beitrag für dich hilfreich?
Dann drück auf .

Johannes S.

Fortgeschrittener

Beiträge: 440

Registrierungsdatum: 24.06.2011

Wohnort: Lychen

Beruf: Beruf?, Schüler

Danksagungen: 71

  • Private Nachricht senden

10

26.06.2011, 18:31

geh mal ein paar wenige Beiträge nach oben, da steht bereits was dazu :D
Signatur ?

Patrick

Profi

Beiträge: 694

Registrierungsdatum: 23.06.2011

Wohnort: Wuppertal

Danksagungen: 168

  • Private Nachricht senden

11

26.06.2011, 18:40

Ein Beitrag über mir ;)
So, habs jetzt mal geändert MIT einrückung :) wirklich viel besser siehts nicht aus...

BTW: Ist das hier nicht ein Fragethread und kein Angebotsthread ;)
Ex ungue leonem.

War der Beitrag für dich hilfreich?
Dann drück auf .

Johannes S.

Fortgeschrittener

Beiträge: 440

Registrierungsdatum: 24.06.2011

Wohnort: Lychen

Beruf: Beruf?, Schüler

Danksagungen: 71

  • Private Nachricht senden

12

26.06.2011, 18:53

Und nochmal zu dir, es ist wahrscheinlich wirklich recht schnell, aber die haben da angefangen mit Multithreadunterstützung und Co XD Und die haben ja auch solche Systeme genutzt XD
Signatur ?

cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

13

26.06.2011, 19:10

oh,
naja
ich meine
wenn man als ziehl nimmt, alle Primzahlen von 2 bis 2157583648 (der maximale Wertebereich von Integer) dann kann man 100 threads Programmieren und es genau aufteilen, von wo bis wo welcher thread die Primzahlen berechnet. Und ja, dann ist es verdammt viel schneller (was aber bei nem Singlecore nicht viel bringt, wieil trotz mehrerer Threads nur ein kern zur verfügung steht.)
Was es halt bringen würde, ist wenn man es direkt Multicore Pogrammiert. Also n Apple Pro mit 12 Kernen, dann 12 Kerne Multicore Programmieren und jeder Kern bekommt dann nochmal 10 Threads. Dann wirds brutalst :D

Drakor

Fortgeschrittener

Beiträge: 204

Registrierungsdatum: 30.06.2011

Danksagungen: 105

  • Private Nachricht senden

14

30.06.2011, 23:00

Öhm,

das ist nicht ganz richtig ... Man kann das Sieb des Erathostenes nicht zu 100% parallelisieren, deswegen heißt doppelte anzahl Cores nicht gleich doppelte Geschwindigkeit... Zumal das Sieb sowieso nur auf in einem threaded-shared-objects Environment läuft und du da Verzögerungen durch die Locks oder dem CAS hast (wobei CAS nur mit hardwareunterstützung passt).

Und bei deinem Java-Code hast du da auch noch die JVM dazwischen.. also ich muss Johannes recht geben, ich glaube nicht (jetzt ohne dein Programm getestet zu haben), dass der Java Code von dir 1 Milliarde Primzahlen in 0,85 Sekunden schafft und selbst das ist noch verbesserbar.

Aber definitiv ne coole Sache, aber ich sag dir gleich: Das Multithreaded zu machen lohnt nicht, das ist nicht nur extrem schwer, sondern bringt wenig bis gar keinen Performancevorteil.

Gruß
Drakor

εδε

Schüler

Beiträge: 77

Registrierungsdatum: 29.06.2011

Wohnort: /home/ede

Beruf: Student

Danksagungen: 27

  • Private Nachricht senden

15

01.07.2011, 06:58

Also ich hab das Sieb des Eratosthenes in Matlab implementiert:

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function [primes, time] = eratosthenes(max_iter)

    primes = ones(1, max_iter);
    primes(1) = 0; 

    tic;
    
    for i = 1:max_iter
        if primes(i)
            for k = i^2:i:max_iter
                primes(k) = 0;
            end;
        end;
    end;
    
    time = toc;
        
    primes = find(primes);
    
end


Leider bricht der Algorithmus für eine Grenze von 1 Milliarde ab, da der Speicher überläuft, aber für 100 Millionen gibt er mir eine benötigte Zeit von ~ 7 Sekunden zurück. (Auf einem Intel Dualcore @ 3.4 Ghz)

Ich denke für größere Grenzen wird das Sieb des Atkins schneller zum Ziel kommen. Ich habe bereits versucht es ebenfalls in Matlab zu implementieren, allerdings läuft das Skript noch deutlich langsamer als das klassische Sieb des Erastothenes.
Theoretisch hat das Sieb des Atkins eine assymptotische Laufzeit von [latex=\mathcal{O}\left(\frac{n}{\log\log{n}}\right)][/latex], also bei effizienter Implementierung schneller gegenüber dem Sieb des Eratosthenes mit einer Laufzeit von [latex=\mathcal{O}\left(n\right)][/latex].

Vielleicht schafft es ja jemand von euch das Sieb des Atkins effizient zu programmieren ^^


"Die Mehrheit bringt der Mathematik Gefühle entgegen, wie sie nach Aristoteles durch die Tragödie geweckt werden sollen, nämlich Mitleid und Furcht. Mitleid mit denen, die sich mit der Mathematik plagen müssen, und Furcht, daß man selbst einmal in diese gefährliche Lage geraten könne."



cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

16

01.07.2011, 14:22

huch :D
Was mach ich anderst?
Ich bekomm 1000000 Primzahlen in 1252 Milisekunden (1.252 Sekunden) berechnet. (System: Laptop mit 1GB RAM und 2x2,1GhZ. ich denke auf einem System mit deutlich mehr Ram und mehr Rechenleistung wirds noch schneller laufen. Ich denke, da könnte man unter eine Sekunde kommen ;) )

Naja, zum Paralellisieren: Ich würde es so machen, dass ich eine Zahl x eben eingeben kann, und dann wird diese durch die Anzahl der Threads geteilt (besser gesagt, gerade Zahlen werden durch 2 oder 4 geteilt, vielfache von 3 werden durch 3 oder 6 geteilt und vielfache durch 5 werden durch 5 geteilt.) Und dann berechnet jeweils ein Thread von zahl y bis z und speichert diese. Danach werden alle Zahlen durch einen Sortieralgorythmus in die richtige reihenfolge gebracht und dann ausgegeben. Die Berechnung der zeit findet dann aber nur für die Berechnung statt und nicht für das Sortieren.

εδε

Schüler

Beiträge: 77

Registrierungsdatum: 29.06.2011

Wohnort: /home/ede

Beruf: Student

Danksagungen: 27

  • Private Nachricht senden

17

01.07.2011, 15:21

Bei einer Grenze von 1 Millionen komme ich auf 0.0534 Sekunden.

Versuch doch mal deine for-Schleife, in den die Vielfachen gestrichen werden etwas zu optimieren:

Java-Quelltext

1
2
for (int j = i*i; j <= max; j+=i)
	isPrim[j] =false;


Die Zahlen kleiner als [latex=i^2][/latex] wurden ja bereits, wegen der Existenz eines kleineren Teilers [latex=k][/latex] , gestrichen.
Könnte eventuell deine Implementierung um einige Millisekunden beschleunigen.


"Die Mehrheit bringt der Mathematik Gefühle entgegen, wie sie nach Aristoteles durch die Tragödie geweckt werden sollen, nämlich Mitleid und Furcht. Mitleid mit denen, die sich mit der Mathematik plagen müssen, und Furcht, daß man selbst einmal in diese gefährliche Lage geraten könne."


Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »εδε« (01.07.2011, 15:27)


εδε

Schüler

Beiträge: 77

Registrierungsdatum: 29.06.2011

Wohnort: /home/ede

Beruf: Student

Danksagungen: 27

  • Private Nachricht senden

18

02.07.2011, 10:34

Schau mal hier: http://download.cnet.com/Prime-Number-Ge…53_4-81386.html
Das müsste funktionieren.

Grüße,
Ede


"Die Mehrheit bringt der Mathematik Gefühle entgegen, wie sie nach Aristoteles durch die Tragödie geweckt werden sollen, nämlich Mitleid und Furcht. Mitleid mit denen, die sich mit der Mathematik plagen müssen, und Furcht, daß man selbst einmal in diese gefährliche Lage geraten könne."



cedi

Profi

  • »cedi« ist der Autor dieses Themas

Beiträge: 706

Danksagungen: 78

  • Private Nachricht senden

19

12.07.2011, 22:52

und was sagt uns das Zitat nun?

Christian

Fortgeschrittener

Beiträge: 373

Registrierungsdatum: 23.06.2011

Wohnort: Lilienthal

Beruf: Schüler

Danksagungen: 82

  • Private Nachricht senden

20

12.07.2011, 23:18

das Zitat ahct irgendwie garkein Sinn. und seine Frage nach einer Datei, die in schnellem Java gecodet ist. naja ich glaube so ein algo ist wenn man in in C schriebt schneller als in Java, das Java ja noch inner VM läuft.

Christian

Zitat

Windows kann entgegen vieler behauptungen kein Virus sein. Denn Viren funktionieren normalerweise und tun etwas Sinnvolles
Wenn Beiträge Hilfreich waren drücke bitte den Bedanken Knopf drücken.

Kein Support per PN oder Mail, wir haben für jede Frage den passenden Bereich.