Alle Primzahlen bis zu einem Maximalwert ermitteln

C :: Aufgabe #46 :: Lösung #1

2 Lösungen

#46

Anfänger - C von devnull - 26.02.2014 um 18:36 Uhr

Es soll ein Programm geschrieben werden, welches alle Primzahlen im Bereich von 2 bis zu einem Maximalwert sucht und auf der Konsole ausgibt.
Den Maximalwert soll der Benutzer beim Programmaufruf auf der Kommandozeile angeben können.
Der Algorithmus zur Primzahlensuche ist frei wählbar.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von devnull (8870 Punkte) - 01.03.2014 um 14:09 Uhr

Der Maximalwert wird aus argv[1] gelesen, ohne numerische Eingabeprüfung.
Defaultwert ist 100. Absoluter Maximalwert ist 1000000 (Array-Limit).

C-Code

/*************************
 * prime.c  Siebmethode
 * devnull  01-03-2014
 *************************/
#include <stdio.h>
#include <stdlib.h>

#define PRIME 1        // Marke Primzahl
#define NOPRIME 0      // Marke Nicht-Primzahl
#define MAX 1000000    // Array Limit

int numbers[MAX+1];
int max_num;

void set_mult_of_prime(int);
int get_next_prime(int);


int main(int argc, char **argv) {
    int next_prime;
    int i;

	max_num = (argc==2) ? atoi(argv[1]) : 100;
	if (max_num > MAX) max_num = MAX;
		
	/* alle Zahlen als PRIME markieren */
    for (i=0; i <= max_num; i++)
        numbers[i] = PRIME;
    numbers[1] = numbers[0] = NOPRIME;    

	/* Schleife bis max_num */
    next_prime = 2;
    do {
        set_mult_of_prime(next_prime);
        next_prime = get_next_prime(next_prime);
    } while (next_prime <= max_num);

    /* Ergebnis auf stdout */
    printf("Primzahlen bis %d:\n", max_num);
    for (i=0; i <= max_num; i++)
        if (numbers[i] == PRIME)
            printf("%d ", i);
    printf("\n");
	return 0;
}

/* alle Vielfache von n auf NOPRIME setzen */
void set_mult_of_prime(int n) {
int m;
    m = n << 1;
    while(m <= max_num) {
        numbers[m] = NOPRIME;
        m += n;
    }
}

/* naechste Primzahl nach n (Marke PRIME) */
int get_next_prime(int n) {
    while(++n <= max_num && numbers[n] == NOPRIME)
        ;
    return n;
}