Primzahler Programm???
-
Hallo
Nun ich habe wieder eine aufgrabe bekommen. Und zwar programmieren sie ein Programm in c das alle Primzahlen von 0-1000 findet. Nun an sich nichts Komisches. Ich wies eine primmzahl ist eine zahl die sich durch eins und durch sich selbst teilen läst. Nun ich habe ein paar primmzahlen mit der hand berechnet und es Kamm heraus.
0,1,2, 3, 5, 7, 11, 13, 17, 19
danach war es mir langweilich geworden und ich habe aufgehört. Nun ich habe mir diese Zahlen seeeeeeeeeeehhhr lange angekuckt und daraus ein paar sahen gezogen.
1)Die erste prim zahl ist die 0 glaube ich???(Stimmt das???)
2)nun nach n>2 sind alle primzahlen 2n+1
3) 1000 ist keine primzahl da 1000 durch 2,5, sicher dividiert wird.
4) Ich habe mir überlekt von 0 bis 9 habe ich 5 prim und von 10-20 habe ich 4 primm
ich kann mich erinnern da gabes auch was ich glaube die meisten primm waren in den kleisten bereichen(ist auch irgentwie logisch)Ich weiss das mache ich mit Euklidischen Algorithmus.
(Direktor der Alexandrische Bibliothek!!!). Nun ich habe was im net gefunden.
Nun ich habe gelesen das der Sieb von eratosfrnis so funktioniert. Ich zeig das mit einer Anwendung:Also die zahlen 0,1,2,3,4,5,…,1000
Wie peewee schon gesagt hat ist zwei die erste prim. Zahl. Nun lösche ich alle zahlen von n<2:
Also habe ich 2,3,4,5,6,7,8,9…,1000 übrig.
Nun nehmen wir behalten wir die zahl 2 und lösche alle seine vielfache also 2,4,6,8…, . Wir nehmen die zahl 3 und löschen alle zahlen die ein vielfaches von 3 ist. Also 6,9,12,…Und ich höre auf von wenn sqrt(1000) stse also auf wurzel von 1000 = 31,6227766 also ich höre auf nach 31. Nun wenn ich das mache bleiben mir nur die brimmzahlen übrig.Nun habe ich bis hier alles richtig verstanden oder funktioniert so nicht das sieb von eratosthenis.
Probleme mit den Sieb:
1)Nun muss ich das bis 31 machen also für die zahlen. 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 oder??
Aber z.b.
6=23
8=24
9=33
12=34
u.s.w.
also habe ich viele zahlen da drin von 0-31. Die ich fuhr die Berechnung aber nicht brauche.
Wie kann ich testen welche Nummer ich brauche und welche nicht??-
diese was ich vorher gesagt habe also alle prim zahlen sind nur 2n-1 stimmt doch oder??
Das kann ich benutzen. So verfeinere ich die menge von Problem eins. -
Ich kann doch mod(das ubrichgebliben von einer euklidische Division und nicht nur
z.b. 5=2*2+1 1 ist mod) hier benutzen damit ich einpaar zahlen herausfiltern kann, dabei aber filtern sich aber auch wichtige zahlen raus wie 2,3, usw.
Und irgendwie kann ich das doch mit diesen komischen mod auch was machen oder??? Nun ich muss ein algoritmus programmieren (wer die suche verkleinert bekommt Extrapunkte) was sagt nun euklidhs???
Bin führ jeden ratschlag offen.Nun ich mus das Prog machen ohne Array zu benutzen wen es geht.
Danke im voraus.Gruss
-
-
1000 ist keine primzahl da 1000 durch 2,5, sicher dividiert wird.
-
Master User schrieb:
Bin führ jeden ratschlag offen.Nun ich mus das Prog machen ohne Array zu benutzen wen es geht.
Nun, das Sieb des Erathostenes hat ja eigentlich genau so eine Struktur, dass man es als Array implementieren würde. Mir ist auch nicht klar, wie man das ohne Array hinkriegt. Zumindest habe ich mal ein Java-Programm geschrieben, in dem das Sieb mit Array implementiert wird. Vielleicht hilft dir das ja schon mal als Grundlage weiter:
public class TestPrime { public TestPrime () { } public static void main (String[] args) { int end = 10000000; long time = System.currentTimeMillis (); int [] sieve = new int [(end >> 5) + 1]; int x, y, i; int primes = 1; int sqrt = (int)Math.sqrt((double)end); x = 3; while (x <= sqrt) { if ((sieve[x >> 5] & (0x1 << (x & 0x1f))) == 0) { y = x * x; i = x << 1; ++primes; while (end > y) { sieve[y >> 5] |= (0x1 << (y & 0x1f)); y += i; } } x += 2; } while (x <= end) { if ((sieve[x >> 5] & (0x1 << (x & 0x1f))) == 0) ++primes; x += 2; } System.out.println ("Zwischen 0 und " + end + " liegen " + primes + " Primzahlen."); System.out.println ("GesamtZeit : " + (System.currentTimeMillis () - time) + " Millisekunden"); } }...da nochmal als C++-Variante(weil ich die gerade wiedergefunden habe):
#include<iostream> #include<time.h> #include <cmath> int main () { const int end = 1000000000; const long startTime = (long)time(NULL); const int arraySize = (end >> 5) + 1; int sieve [arraySize]; for (int i = 0 ; i < arraySize ; ++i) { sieve[i] = 0; } int x, y, i; int primes = 1; const int sqrtEnd = (int)sqrt((double)end); x = 3; while (x <= sqrtEnd) { if ((sieve[x >> 5] & (0x1 << (x & 0x1f))) == 0) { y = x * x; i = x << 1; ++primes; while (end > y) { sieve[y >> 5] |= (0x1 << (y & 0x1f)); y += i; } } x += 2; } while (x <= end) { if ((sieve[x >> 5] & (0x1 << (x & 0x1f))) == 0) ++primes; x += 2; } std::cout << "Zwischen 0 und " << end << " liegen " << primes << " Primzahlen." << std::endl; std::cout << "GesamtZeit : " << ((long)time(NULL) - startTime) << " Sekunden" << std::endl; }Wenn du kein Array nehmen darfst, dann mußt du vermutlich einen ganz anderen Algorithmus wählen. Zum Beispiel etwas einfaches, wie das:
import java.io.*; class PrimeCheck { public static void main(String[] args) { long time = System.currentTimeMillis (); int Ende = 1000000; int i = 800000; int j; boolean prime; int sqrt; if ((i & 0x00000001) == 0) ++i; PrintStream outStream = new PrintStream (new BufferedOutputStream (System.out)); while (i < Ende) { i += 2; prime = true; sqrt = (int)Math.sqrt(i); for (j = 3; j <= sqrt ; j+=2) { if (i % j == 0) prime = false; if (!prime) break; } if (prime) outStream.println(i); } outStream.println("\nBerechnung abgeschlossen."); time = System.currentTimeMillis () - time; outStream.println("\nZeit : " + time + "ms"); outStream.flush(); } }Ich hoffe, das hilft dir weiter.
-
#include <stdio.h> int main() { int j,i; int primzahl; printf("\n2"); for (j=3;j<=1000;j+=2) { primzahl=1; for(i=3;i*i<=j;i+=2) { if (j%i==0) { primzahl=0; break; } } if(primzahl) printf("\n%d",j); } }Man kann das Programm noch beschleunigen. Der Code wird dann aber länger.
#include <stdio.h> int main() { int j,i; int primzahl; printf("\n2\n3"); for (j=5;j<=1000;j+=4) { primzahl=1; for(i=5;i*i<=j;i+=4) { if (j%i==0) { primzahl=0; break; } i+=2; if(i*i>j) break; if (j%i==0) { primzahl=0; break; } } if(primzahl) printf("\n%d",j); j+=2; if(j>1000) break; primzahl=1; for(i=5;i*i<=j;i+=4) { if (j%i==0) { primzahl=0; break; } i+=2; if(i*i>j) break; if (j%i==0) { primzahl=0; break; } } if(primzahl) printf("\n%d",j); } }Die zeite Version ist ca. 4 mal schneller als die erste, wenn man die printf Befehle entfernt.
Man kann es auf die gleiche Weise auch noch weiter beschleunigen.
-
Master User schrieb:
0,1,2, 3, 5, 7, 11, 13, 17, 19
Weder 0 noch 1 sind Primzahlen. 0 ist durch jede natuerliche Zahl teilbar (also durch weniger als 2), 1 ist durch genau eine natuerliche Zahl teilbar (sich selber). Die Definition sagt aber, dass Primzahlen durch genau zwei natuerliche Zahlen teilbar sein sollen.
-
Leute wirklich danke man. Aber hat euch keiner gesagt das man in ein programm viele komentare schreiben soll.
wie z.b.
//HALLO
/*HALLO*/schon und gut alle programme aber ich weis nicht was da steht (auf den ersten blik) ich lade sie herunter und schau sie mir mal an. Danke leute echt net von euch ich schulde euch allen ein Bier danke danke leute.
-
geb ich auch noch meinen Senf dazu, die ganz, ganz simple Variante Primzahlen zu suchen:
das ganze verwendet double's statt ints, damit man auch richtig grosse Zahlen verwenen kann... sowas wie __int64 kannte ich damals noch nicht *g*
double isPrimeNumber(double& dblNumber) /******************************************** TAKES: dblNumber: Double to test RETURNS: Number dividing dblNumber *********************************************/ { double dblSquare; dblSquare = sqrt(dblNumber); // special handling for the Number "2" if ((dblNumber / 2) * 2 == dblNumber) return 2; for(double j = 3; j <= dblSquare; ++j) if ((dblNumber / j) * j == dblNumber) return j; return 0; // return 0 if dblNumber could not be divided (= IS A PRIME NUMBER!!!) }EDIT: das Stueck Code ist schon ziemlich alt, also bitte kein Gemecker vonwegen schlechter Coding-Stil oder so...
-
Ich habe heute mein lehrer gefragt und er sgte man kann das mit den sieb des euklidis berchnen. Aber wie. danke leute ihr seit wirklich nett
-
@Blue-Tiger: Dein Code funktioniert nicht. Gibt es überhaupt eine Zahl, die dein Code als Primzahl erkennt?
-
Master User schrieb:
Ich habe heute mein lehrer gefragt und er sgte man kann das mit den sieb des euklidis berchnen. Aber wie. danke leute ihr seit wirklich nett
Ich glaube nicht, dass es ein "Sieb des Euklids" gibt. Er meint sicherlich das Sieb des Erathostenes. Das entspricht den oberen beiden von mir gezeigten Programmen.
-
Gregor schrieb:
@Blue-Tiger: Dein Code funktioniert nicht. Gibt es überhaupt eine Zahl, die dein Code als Primzahl erkennt?
humm... kann gut sein, ich hab den Code aus einem Uralt-Projekt, und selbst da war er auskommentiert...
Aber tausch mal alle "double" durch int's aus, dann sollte es gehen.... behaupt ich einfach mal auf den 1. Blick
-
Blue-Tiger schrieb:
Aber tausch mal alle "double" durch int's aus, dann sollte es gehen.... behaupt ich einfach mal auf den 1. Blick
Ist diese Bedingung wahr oder falsch:
x/y*y == x
-
hallo!
google mal nach sieb des Eratosthenes .
Viel spass
-
@Shade: ohne Klammerung?
-
Shade Of Mine schrieb:
Blue-Tiger schrieb:
Aber tausch mal alle "double" durch int's aus, dann sollte es gehen.... behaupt ich einfach mal auf den 1. Blick
Ist diese Bedingung wahr oder falsch:
x/y*y == x
die Bedingung ist wahr, wenn y Teiler von x ist.... Vorrausgesetzt, x und y sind int, sonst nur wenn man
int(x/y) * y == x
macht und y nur natuerliche Zahlen sind... ist eine andere Moeglichkeit,
x % y == 0
zu schreiben
-
google googlet sich in seiner nasse