010
28.09.2003, 14:04 Uhr
Pablo
Supertux
(Operator)
|
So, das ist das letzt was mir einfällt. Natürlich kann man das eine oder andere verbessern, aber ich hab es so gemacht, damit es jeder verstehen kann, auch wenn man wenig Erfahrung hat.
Das ist dynamisch, die Art, wie man das Array erstellt kann man verbessern, werde ich aber nicht tun, vielleicht hat hier der eine oder der andere eine bessere Idee als meine und postet auch seine Lösung. Meine wäre:
| C++: |
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
int* array;
int arrcount;
int istprim(unsigned int zahl)
{
int i=1, j; // angegeben, die Zahl ist prim.
if(zahl==0) return -1;
if(zahl==1) return 0; // 1 ist keine primzahl
if(zahl==2 || zahl==3 || zahl==5) return 1; //damit for schleife keine Probleme kriegt
if(!(zahl%2)) return 0; // wenn positiv außer 2, dann ist nicht prim
for (j=3; j<zahl/2; j=j+2) // wir brauchen nur bis zur Hälfte gehen
i *= (zahl % j > 0);
return i;
}
int erfuellt_eigenschaft(unsigned int zahl, int* a, int *b)
{
int i, counter=0, z=pow(zahl,2)-1;
// ich gehe davon aus, dass 0 nicht übergeben wird, sonst kann das eklig werden
// für die Primzahlen 2, 3 wissen wir, dass sie die Eigenschaft nicht erfüllen (1)
// für die Primzah und 5 folgt aus (1) dass sie die Eigenschaft nicht erfüllen, weil
// 5^2=25 ist weder von 2, 3 teilbar ist, also können wir diese sofort ausgeben
if(zahl == 2 || zahl == 3 || zahl == 5) return 0;
// wenn wir hier ankommen, ist weil die Primzahl >= 7 ist, also mindestens 3 Primzahlen
for(i=0; i<arrcount; ++i) {
if(!(z % array[i])) {
if(counter==0) *a=array[i];
if(counter==1) *b=array[i];
counter++; // zahl^2-1 ist diese Primzahl teilbar
}
if (counter>2) return 0; //wenn es mehr als 2 sind, brauche wir nicht mehr alle andere Primzahlen
}
return 1;
}
int main(int args, char** argv)
{
int i, j=0,x,y, a,b, begin;
if (args != 3) {
printf("usage: %s x y\nx und y sind die Grenzen des Intervalls. Das Interval soll eine Teilmenge der Natürlichen Zahlen |N sein\n", argv[0]);
return 0;
}
// das Programm wird nicht untersuchen, ob die Parameter zahlen sind
// ich geh davon aus, dass sie Zahlen sind, hoffe ich :)
x=atoi(argv[1]);
y=atoi(argv[2]);
if(y<x) {
printf("Das eingebene Interval [%d,%d] ist mathematisch nicht korrekt.\n", x,y);
return 0;
}
// Das array wird zuerst initialisiert, das Array wird mindestens 1Feld haben
array = (int*)malloc(sizeof(int));
arrcount=0;
// Hier fängt alles an
// array initialisieren:
printf("Creating array....\n");
for(i=1;i<=y; ++i) {
if(istprim(i)==1) {
array=realloc(array, (++arrcount)*sizeof(int));
array[arrcount-1] = i;
if (x > i) begin=arrcount;
}
}
if (x<=2) begin=0;
printf("Array created\n");
for(i=begin; i<arrcount; ++i) {
j = erfuellt_eigenschaft(array[i],&a,&b);
if(j)
printf("Die Primzahl %d erfüllt die Eigenschaft. Die anderen Primzahlen sind %d und %d\n",array[i],a,b);
j=0;
}
/*for(i=begin; i<arrcount; ++i)
printf("array[%d] = %d\n", i, array[i]);*/
free(array);
return 0;
}
|
Für das Interval [0; 10000] rechnet mein Rechner 1 Sekunde.
Für das Interval [0; 100000] hat mein Rechner aber 38 Sekunden gebraucht, und die Ausgabe hat 4802 Zeilen, also 4802 Primzahlen gefunden.
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!
Dieser Post wurde am 28.09.2003 um 14:08 Uhr von Pablo Yanez Trujillo editiert. |
ausserdem p > 3. Dann ist p^2 - 1 = (p + 1)(p - 1), und weil darin p ungerade war, sind p - 1 und p + 1 teilbar durch 2, weil p nicht durch drei teilbar war, ist entweder p - 1 oder p + 1 teilbar durch drei. Insgesamt haben wir also für p^2 - 1 im Fall p > 3 schonmal _mindestens_ zwei verschiedene Primteiler.