C-Code für Sieb von Erasthenes

Question

Kann mir bitte jemand sagen, warum mein Programm alle Primzahlen bis zur Eingabe n ausgibt und auch nur die Nummer n+2 (ob prime oder nicht)? Und manchmal auch n+1, wenn es prim ist, z.B. Für die Eingabe n=10 ist die Ausgabe 2,3,5,7,11,12.

ist hier mein Code:

/*Write a program that reads in a number n between 1 and 100,000 and then lists all the prime numbers between 1 and n inclusive.*/ 

#include 

#define LIMIT 100000 /*size of integers array*/ 
#define PRIMES 100000 /*size of primes array*/ 

int main(){ 
    int i,j,numbers[LIMIT]; 
    int primes[PRIMES]; 
    int n, count; 
    count = 0; 

    /*Read in an upper limit, n*/ 
    printf("Please enter a value for n: "); 
    if (scanf("%d", &n) !=1) { 
     printf("Sorry, cannot read n.\n"); 
     return 1; 
    } 

    /*fill the array with natural numbers*/ 
    for (i=0;i<=n;i++){ 
     numbers[i]=i+2; 
    } 

    /*sieve the non-primes*/ 
    for (i=0;i<=n;i++){ 
     if (numbers[i]!=-1){ 
      for (j=2*numbers[i]-2;j<n;j+=numbers[i]) 
       numbers[j]=-1; 
     } 
    } 

    /*transfer the primes to their own array*/ 
    j = 0; 
    for (i=0;i<=n&&j<PRIMES;i++) 
     if (numbers[i]!=-1) { 
      primes[j++] = numbers[i]; 
      count = count + 1; } 

    /*print*/ 
    for (i=0;i<count;i++) 
     printf("%d\n",primes[i]); 

    return 0; 
} 

Answer 1

Sie immer n setzen + 1 und n + 2 in Ihren Zahlen Array,

for (i=0;i<=n;i++){ 
    numbers[i]=i+2; 
} 

Für i in {n-1, n}.

Aber Sie sie nicht herausfiltern, Da dieser Schleife:

for (i=0;i<=n;i++){ 
    if (numbers[i]!=-1){ 
     for (j=2*numbers[i]-2;j<n;j+=numbers[i]) 
      numbers[j]=-1; 
    } 
} 

Ignoriert die Zahlen, die als n größer sind.

Eine Arbeitsversion:

#define MAX_SIZE 100000 /*size of integers array*/ 

int main() { 
    unsigned int i; 
    unsigned int j; 
    unsigned int max_filled_index; 
    unsigned int numbers[MAX_SIZE]; 
    unsigned int primes[MAX_SIZE]; 
    unsigned int num_to_sieve; 
    unsigned int prime_count = 0; 

    /*Read in an upper limit, n*/ 
    printf("Please enter a value for n: "); 
    if (scanf("%d", &num_to_sieve) != 1) { 
     printf("Sorry, cannot read n.\n"); 
     return 1; 
    } 

    max_filled_index = num_to_sieve - 2; 
    /*fill the array with natural numbers*/ 
    for (i = 0; i <= max_filled_index; i++) { 
     numbers[i] = i + 2; 
    } 


    /*sieve the non-primes*/ 
    for (i = 0; i <= max_filled_index; i++) { 
     if (numbers[i] != 0) { 
      for (j = 2 * numbers[i] - 2; j <= max_filled_index; j += numbers[i]) { 
       numbers[j] = 0; 
      } 
     } 
    } 

    /*transfer the primes to their own array*/ 
    for (i = 0; i <= max_filled_index && prime_count < MAX_SIZE; i++) 
     if (numbers[i] != 0) { 
      primes[prime_count] = numbers[i]; 
      prime_count++; 
     } 

    /*print*/ 
    for (i = 0; i < prime_count; i++) 
     printf("%d\n", primes[i]); 

    return 0; 
}