Programm schreiben das Primzahlen mithilfe von Arrays herausfindet?
Hallo,
muss eine Funktion in C schreiben, die Primzahlen in einem Array herausfindet. Wie macht man sowas ohne, dass man Pointer verwenden darf?
2 Antworten
Was ich aus der Aufgabe verstehe:
Gesucht ist ein Programm, welches wie "Das Sieb des Eratosthenes" ein Array of Boolean hat, in dem erst mal jede Zahl als Primzahl angenommen wird.
Dann werden die Vielfachen von Primzahlen als False markiert.
Übrig bleiben die Primzahlen, welche weiterhin mit True markiert sind.
Nein hab ich vielleicht ein bisschen dumm formuliert: siehe Antwort von @linearealgebruh
Wie genau meinst du das "Primzahlen in einem Array"? Bekommst du einfach ein Array, der gefüllt ist mit random Zahlen und du musst herausfinden, welche von diesen Zahlen Primzahlen sind? Da nimmst du einfach eine Schleife und gehst jeden Index durch und machst den "naiven" Primzahltest, in dem du einfach mithilfe einer weiteren Schleife alle Zahlen unter deiner Zahl n abklapperst und überprüfst ob die Zahl ein Teiler von n ist (mithilfe der modulo Operation %).
Oder möchtest du die Primzahlen bis zu einem bestimmten n ausgegeben haben? Da könnte man das sehr gut mit dem Sieb des Erastothenes und einem Array, der Bools enthält, machen
Ich hab so ein Programm gestern geschrieben, aber in C++ und mithilfe von Pointern, kann es dir aber trotzdem schicken wenn du magst
Ich meinte ersteres. Alles klar habs mir schon so ähnlich gedacht, aber wusste nicht das man die Stellen eines Arrays auch ohne Pointer auslesen kann :) Danke werd es jetzt mal versuchen, wenn ich es nicht hinbekomm, darf ich mich dann wieder bei dir melden?
Du kannst doch die Länge eines Arrays ausgeben lassen mit "(int) sizeof(NameVomArray)" wenn ich mich recht entsinne
Ja aber das gibt ja immer ein Warning mit Clang und ich darf den Sourcecode nicht abgeben wenn ein Warning beim Kompilieren entsteht. Allerdings glaub ich auch, dass die Aufgabenstellung anders gemeint ist.
Ich habs jetzt mal so gemacht :
--------------------------------------------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <inttypes.h>
unsigned int countPrimes(uint32_t element_list[], unsigned int elements)
{
int a;
int b = 0;
for (size_t i = 0; i <= elements; i++)
{
a = element_list[i]%element_list[i];
if (a == 0)
{
b++;
}
}
return b;
}
int main(void){
uint32_t AnzahlPrimzahlen = countPrimes({2,3,5,7,6,8,10}, 7);
//----------------------------------------------------------------------------------------------------------------------------------
//dieser Ausdruck ist aber falsch. Wie gebe ich Arrays in Rechenoperationen ein //bei //denen eine Funktion verwendet wird?
//---------------------------------------------------------------------------------------------------------------------------------
printf("%d", AnzahlPrimzahlen);
return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------
Mit einem break; , am Besten nach einem if (...)
Ein break bricht for, while, do-while-Schleifen ab.
Willst du nur eine Wert überspringen und den nächsten in der Schleife bearbeiten, dann nimmst du: continue;
Und wie übergebe ich ein Array der Funktion im Operator?
uint32_t AnzahlPrimzahlen = countPrimes({hier sollte das Array stehen}, 7);
Wie gebe ich hier das Array ein? wenn ich einfach element_list[] reinschreibe gibts nen Error.
Wo ist denn die Warnung?
So einige Statements finde ich, können verbessert werden.
- for (size_t i = 0; i <= elements; i++): elements ist 'unsigned int', i ist size_t. Das macht normalerweise nichts, sollte aber zum Abgeben gleich sein.
- element_list[i]%element_list[i];: das verstehe ich nicht. Hier sollte wohl eine Schleife, die gegen kleine Zahlen prüft, ob die kleinere Zahl element_list[i] teilt.
- countPrimes liefert ein unsigned int, im return Statement ist ein int.
- Der Funktionswert von countPrimes() wird dann einem uint32_t zugewiesen.
- %d ist für signed int, du solltest dann %u nehmen.
Ein array wird normalerweise als Pointer auf das erste Element übergeben.
Versuche mal uint32_t * element_list in der Parameter-Deklaration. Beim Zugriff mit [i] brauchst du nichts zu ändern.
Um klar zu machen, dass die Funktion countPrimes() die Daten nicht ändert, kannst du: const uint32_t * element_list schreiben. Bei Pointern gehört da noch ein zweites const rein, damit nicht nur der Pointer sondern auch die Werte hinter dem Pointer nicht verändert werden können.
Habe mal was runter geschrieben, anhand deines Codes. In meinem Stil.
Leider habe ich keinen Compiler hier.
#include <stdio.h>
bool isPrime( unsigned int value )
{
unsigned int test = 2;
while ( test * test <= value )
{
if ( ( value % test ) == 0 )
return false;
test++;
}
return true;
}
unsigned int countPrimes( unsigned int * elementList,
size_t cntElements )
{
unsigned int cntPrimes = 0;
for ( size_t i = 0; i <= cntElements; i++ )
{
if ( isPrime( elementList[i] ) )
cntPrimes++;
} // for
return cntPrimes;
}
int main(void)
{
unsigned int testDaten [] = {2,3,5,7,6,8,10};
size_t cntElements = sizeof( testDaten ) / sizeof( testDaten[0] );
unsigned int cntPrimes = countPrimes( testDaten, cntElements );
printf( "%u\n", cntPrimes );
return 0;
}
Habe doch noch compilieren können. Mein Programm gibt eine 4 aus.
Fast: sizeof() gibt die Anzahl der Bytes an. Wenn ein int 4 Bytes hat, dann muss man den Wert noch durch 4 teilen.
Oder so:
size_t cntElements = sizeof( testDaten ) / sizeof( testDaten[0] );
for ( size_t i = 0; i <= cntElements; i++ ) ist falsch. Habe ich so übernommen.
Da bei 0 angefangen wird zu zählen, darf der Index cntElements nicht mehr verwendet werden. Die Zeile muss lauten:
for ( size_t i = 0; i < cntElements; i++ )
Danke erstmal für die mega ausführlichen Antworten :) Problem ist halt ich darf nicht mit bool usw. arbeiten. Ich darf nicht einmal Pointer in dieser Aufgabe verwenden.
Bool kannst du problemlos durch int ersetzen.
Wegen der Pointer überlege ich noch mal.
Läuft es bei Dir?
Mach die Variablen testDaten [] und cntElements doch global, gleich hinter dem #include.
Das Setzen von cntElements machst du in main(), von testDaten bei der Variablendeklaration.
Dann braucht countPrimes() keine Parameter zu, weil die Methode auf die module-globale Variablen zugreift.
Bei mir kann ich zwar mittlerweile kompilieren aber ich bekomm derzeit keinen Output. Bin aber dran das noch zu lösen. Vor allem glaube ich, dass ich meinen Algorithmus noch verfeinern muss. Hätte jetzt mal die Grundidee vom Sieb des Eratosthenes genommen, allerdings erscheint mir das nicht sehr effektiv :/
So sieht die Funktion jetzt aus, komme aber leider nicht mehr weiter :/
-------------------------------------------------------------------------------------------------------------------------------------
unsigned int countPrimes(uint32_t element_list[], unsigned int elements)
{
uint32_t a;
uint32_t b;
uint32_t c;
uint32_t d;
uint32_t x;
uint32_t cntelements = (sizeof(element_list)/sizeof(element_list[0]));
for (unsigned int i = 0; i < 8; i++)
{
x = element_list[i];
if (x != 2 || x != 3 || x != 5 || x != 7)
{
cntelements- -;
}
}
for (unsigned int i = 8; i < elements; i++)
{
a = element_list[i]%2;
b = element_list[i]%3;
c = element_list[i]%5;
d = element_list[i]%7;
if (a == 0 || b == 0 || c == 0 || d == 0)
{
cntelements- -;
}
}
return cntelements;
}
--------------------------------------------------------------------------------------------------------------------------------------
Kann man das so machen? Hab leider keine Möglichkeit wie ich die Funktionsweise überprüfen könnte. Zumindest weiß ich nicht wie ich das mit der Main Funktion überprüfen könnte.
Warum behandelst du die ersten 8 Elemente anders?
In den ersten 8 Elementen können auch Werte > 1 Million stehen.
Außerdem findest du nur Primfaktoren 2, 3, 5 und 7
Warum verwendest du nicht den Code aus isPrime(), den ich gepostet habe?
Der hat keine Größenbegrenzung.
Ich hatte da wirklich nen dummen Denkfehler. Hab nicht bedacht, dass es mehr Faktoren als diese paar gibt (schäm). Kurz zu meiner Idee: Wollte eigentlich Elemente mit Werten unter und über 8 voneinander trennen, da ja zB 2/2 auch 0 ergibt und mir von cntelements abgezogen werden würde. Hätte das aber anders schreiben müssen, da ich nicht bedacht habe, dass ich ja nur die ersten 8 Stellen auslese und nicht die eigentlichen Werte die ich haben wollte :/
Naja ich will irgendwie nicht copy pasten. Will irgendwie mein eigenes Ding finden auf das ich stolz sein kann :D Nur bin ich halt ziemlich übler Anfänger in C deshalb tu ich mich schon ein bisschen schwer damit :/ Wenn mein nächster Versuch aber wieder nicht funktioniert greife ich gerne auf deinen Code zurück :)
Auch ich hab anfänglich massenhaft Fehler gemacht. Die Übung bringt es.
Bei dir müsste glaub ich aber die bool funktion so lauten oder? Sonst werden doch ein paar Werte ausgelassen, wenn ich zum Beispiel nur eine Zahl im Array stehen habe oder vertu ich mich da??
bool isPrime( unsigned int value )
{
unsigned int test = 0;
unsigned int parameter = 2;
while ( test * test <= value )
{
if ( ( value % parameter ) == 0 && value != 2)
{
return false;
}
else if (value == 0 || value == 1)
{
return false;
}
test++;
}
return true;
}
Ok ist noch immer falsch aber jetzt sollt er stimmen :)
bool isPrime( unsigned int value )
{
unsigned int test = 0;
unsigned int parameter = 2;
while ( test * test <= value )
{
parameter*parameter;
if ( ( value % parameter ) == 0 && value != 2 && value != 3)
{
return false;
}
else if (value == 0 || value == 1){
return false;
}
test++;
parameter++;
}
return true;
}
Hallo Maximum,
habe mir mal deine Implementierung angesehen und werde ohne ein Blatt vor den Mund zu nehmen aufschreiben, was mir auffällt. Es geht nur gegen den Quelltext:
- Die Variablen test und parameter sollen wohl das gleiche machen. Die bilden den Divisor. Da reicht eine. Namensvorschlag: divisor
- Die if-Abprüfung "if (value == 0 || value == 1)" kann außerhalb der while-Schleife, da sie nicht von test bzw. parameter abhängt. Hier kann auch mit <2 geprüft werden.
- Hinter einem 'return' braucht man kein else. Das ist Geschmackssache
- Der Ausdruck "parameter*parameter;" ist gültige C-Syntax, macht nur nichts. Er berechnet den Wert und lässt das Ergebnis fallen.
- Die Abprüfung "&& value != 2 && value != 3" kann auch außerhalb der Schleife stehen. Am besten prüfst du vor dem while erst, ob <2 und springst dann mit false raus. Danach prüfst du mit <4 und springst ggfs. mit true raus.
Ok hab das ganze jetzt mal umgeschrieben. Bis zu ein paar Zahlen funktionierts ohne Probleme, aber bei diesem Beispiel kommt 194 raus obwohl 0 rauskommen sollte (ich darf in der Aufgabe nur eine Funktion verwenden) :/
--------------------------------------------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <inttypes.h>
unsigned int countPrimes(uint32_t element_list[], unsigned int elements)
{
unsigned int F;
unsigned int divisor = 2;
unsigned int cntPrimes = 0;
for ( size_t i = 0; i < elements; i++ )
{
if(element_list[i] < 2)
{
F = 0;
}
else if(element_list[i] < 4)
{
cntPrimes++;
}
while ( divisor * divisor <= element_list[i] )
{
if ( ( element_list[i] % divisor ) == 0)
{
F=0;
break;
}
else
{
cntPrimes++;
break;
}
divisor++;
}
}
return cntPrimes;
}
int main(void)
{
unsigned int testDaten [] = {0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28,
30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54,
55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78,
80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102,
104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121,
122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140,
141, 142, 143, 144, 145, 146, 147, 148, 150, 152, 153, 154, 155, 156, 158,
159, 160, 161, 162, 164, 165, 166, 168, 169, 170, 171, 172, 174, 175, 176,
177, 178, 180, 182, 183, 184, 185, 186, 187, 188, 189, 190, 192, 194, 195,
196, 198, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 212, 213,
214, 215, 216, 217, 218, 219, 220, 221, 222, 224, 225, 226, 228, 230, 231,
232, 234, 235, 236, 237, 238, 240, 242, 243, 244, 245, 246, 247, 248, 249,
250, 252, 253, 254, 255, 256, 258, 259, 260, 261, 262, 264, 265, 266, 267,
268, 270, 272, 273, 274, 275, 276, 278, 279, 280, 282, 284, 285, 286, 287,
288, 289, 290, 291, 292, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303,
304, 305, 306, 308, 309, 310, 312, 314, 315, 316, 318, 319, 320, 321, 322,
323, 324, 325, 326, 327, 328, 329, 330, 332, 333, 334, 335, 336, 338, 339,
340, 341, 342, 343, 344, 345, 346, 348, 350, 351, 352, 354, 355, 356, 357,
358, 360, 361, 362, 363, 364, 365, 366, 368, 369, 370, 371, 372, 374, 375,
376, 377, 378, 380, 381, 382, 384, 385, 386, 387, 388, 390, 391, 392, 393,
394, 395, 396, 398, 399, 400, 402, 403, 404, 405, 406, 407, 408, 410, 411,
412, 413, 414, 415, 416, 417, 418, 420, 422, 423, 424, 425, 426, 427, 428,
429, 430, 432, 434, 435, 436, 437, 438, 440, 441, 442, 444, 445, 446, 447,
448, 450, 451, 452, 453, 454, 455, 456, 458, 459, 460, 462, 464, 465, 466,
468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 480, 481, 482, 483,
484, 485, 486, 488, 489, 490, 492, 493, 494, 495, 496, 497, 498, 500, 501,
502, 504, 505, 506, 507, 508, 510, 511, 512, 513, 514, 515, 516, 517, 518,
519, 520, 522, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535,
536, 537, 538, 539, 540, 542, 543, 544, 545, 546, 548, 549, 550, 551, 552,
553, 554, 555, 556, 558, 559, 560, 561, 562, 564, 565, 566, 567, 568, 570,
572, 573, 574, 575, 576, 578, 579, 580, 581, 582, 583, 584, 585, 586, 588,
589, 590, 591, 592, 594, 595, 596, 597, 598, 600, 602, 603, 604, 605, 606,
608, 609, 610};
size_t elements = sizeof( testDaten ) / sizeof( testDaten[0] );
unsigned int cntPrimes = countPrimes( testDaten, elements );
printf( "%u\n", cntPrimes );
}
Ahh ich glaub ich habs, sobald er einen rest bekommt springt er gleich ins else rein also sobald beim ersten versuch ein rest bleibt wird die else bedingung ausgeführt
Muss gleich los, daher habe ich nur einen kurzen Blick drüber geworfen.
Die Variable divisor muss am Anfang der Schleife immer auf 2 gesetzt werden. Sonst hat sie noch den Wert vom vorigen Schleifenelement.
Bin in 1h wieder da.
Hmm ich bin glaub ich zu blöd dafür, darf ich dich nochmal stören? Also der Code wirft mir ab einer bestimmten Zahlengröße ab und zu eine Primzahl aus auch wenns keine ist. Ich vermute, dass die else Schleife manchmal ausgeführt wird, wenn sie nicht ausgeführt werden sollte. Wie behebe ich das Problem? hab schon so ziemlich alles mir bekannte ausprobiert, aber ich geb jetzt nach 5 stunden herumprobieren glaub ich auf :(
Habe nun mal die Methode countPrimes() genau angesehen und umgeschrieben. Bei mir funktioniert es.
Bei dir ist
else
{
cntPrimes++;
break;
}
falsch. Wenn die erste Prüfung keine Faktor liefert, verlässt du mit einem break die while-Schleife. Dabei musst du noch weiter bis zur Bedingung divisor * divisor <= element_list[i] testen.
=======================================================
unsigned int countPrimes( uint32_t element_list[], unsigned int elements )
{
unsigned int divisor;
unsigned int cntPrimes = 0;
for ( size_t i = 0; i < elements; i++ )
{
if ( element_list[i] < 2 )
continue;
if ( element_list[i] < 4 )
{
cntPrimes++;
continue;
}
divisor = 2;
bool isPrime = true;
while ( divisor * divisor <= element_list[i] )
{
if ( ( element_list[i] % divisor ) == 0)
{
isPrime = false;
printf( "%u %% %u = %u\n", element_list[i], divisor, element_list[i] / divisor );
break;
}
divisor++;
} // while
if ( isPrime )
cntPrimes++;
} // for
return cntPrimes;
}
ahhh naja jetzt weiß ich aufjedenfall was ich für fehler eingebaut habe. Vielen dank nochmal, dass du dir zeit genommen hast, ist ja nicht selbstverständlich :)
Hast du es auch verstanden, so, dass es das nächste Mal einfacher ist?
War nett mir dir. Erinnerte mich an meine ersten Schritte in C.
Schönen Sonntag.
Ok hab es jetzt mal versucht aber wie kann ich meine for Schleife abbrechen wenn die max Elemente vom Array erreicht wurden? Die Anzahl der Elemente im Array kann ja je nach main Funktion variieren. Wie löst man sowas?