006
28.09.2003, 13:01 Uhr
Pablo
Supertux
(Operator)
|
Wie wäre es damit?
| C++: |
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
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) // wir brauchen nur bis zur Hälfte gehen
i *= (zahl % j > 0);
return i;
}
int erfuellt_eigenschaft(unsigned int zahl)
{
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=2; i<zahl; ++i) {
if (istprim(i)) {
if(!(z % 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;
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 sein\n");
return 0;
}
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 Programm wird nicht untersuchen, ob die Parameter zahlen sind
// ich geh davon aus, dass sie Zahlen sind, hoffe ich :)
// Hier fängt alles an
for(i=x; i<=y; ++i) {
// ist das prim ?
if (istprim(i)==1)
j = erfuellt_eigenschaft(i);
if(j)
printf("Die Primzahl %d erfüllt die Eigenschaft\n",i);
j=0;
}
return 0;
}
}
|
Man muss das Interval beim Ausführen übergeben
programprimzahl 0 100
Läuft alles in O(n^2), ungefähr, das kann ich natürlich verbessern, gibt mir nur Zeit.
| Code: |
.
/prim 0 10000
Die Primzahl 7 erfüllt die Eigenschaft
Die Primzahl 17 erfüllt die Eigenschaft
|
Im Interval [0, 10000] gab es nur die 7 und die 17, die das erfüllt haben, umd Interval [0, 100000] gibt es noch mehrere, aber das Programm rechnet ja immer noch.
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!
Dieser Post wurde am 28.09.2003 um 13:08 Uhr von Pablo Yanez Trujillo editiert. |
