C-Programmierung
Sieb des Eratosthenes
← Speicherverwaltung: Memset, Realloc etc. | ● | Header und Module →
Bestimmung von Nicht-Primzahlen durch Austreichen aller Vielfachen 2p 3p 4p … einer Zahl p.
Die übrig bleibenden nicht ausgestrichenen Zahlen des Zahlenstrahls sind Primzahlen.
Vielfache von 2 ausstreichen:
| nicht-prim | x | x | x | x | x | x | x | x | x | … | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Zahlenstrahl | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | … |
Vielfache von 3 ausstreichen:
| nicht-prim | x | x | x | x | x | x | x | x | x | x | x | x | … | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Zahlenstrahl | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | … |
Vielfache von 4 ausstreichen: 4 ist nicht prim, alle Vielfachen sind bereits markiert!
Vielfache von 5 ausstreichen:
| nicht-prim | x | x | x | x | x | x | x | x | x | x | x | x | … | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Zahlenstrahl | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | … |
usw.
C Code-Fragment:
int n;
bool *notprime;
printf("calculate prime numbers up to:");
scanf("%d", &n);
notprime=(bool *)calloc(n+1, sizeof(bool));
assert(notprime);
for (int i=2; i<=n; i++)
if (!notprime[i])
{
printf("%d is prime\n", i);
for (int j=2*i; j<=n; j+=i) notprime[j]=TRUE;
}
free(notprime);
bool *notprime;
printf("calculate prime numbers up to:");
scanf("%d", &n);
notprime=(bool *)calloc(n+1, sizeof(bool));
assert(notprime);
for (int i=2; i<=n; i++)
if (!notprime[i])
{
printf("%d is prime\n", i);
for (int j=2*i; j<=n; j+=i) notprime[j]=TRUE;
}
free(notprime);
← Speicherverwaltung: Memset, Realloc etc. | ● | Header und Module →