C: Сито Эратосфена с использованием массивов - PullRequest
Новая
       17

C: Сито Эратосфена с использованием массивов

2 голосов
/ 19 марта 2012

Я работаю над заданием по программированию на C для реализации Sieve of Eratosthenes без использования функции квадратного корня из C. Ниже приведены мои выходные данные и выходные данные моих профессоров, я не уверен, что в моем коде вызывает ошибку.Есть идеи?

Вот ожидаемый результат 

Program initiated
   1   2   3   5   7  11  13  17  19  23  29  31
  37  41  43  47  53  59  61  67  71  73  79  83
  89  97 101 103 107 109 113 127 131 137 139 149
 151 157 163 167 173 179 181 191 193 197 199 211
 223 227 229 233 239 241 251 257 263 269 271 277
 281 283 293 307 311 313 317 331 337 347 349 353
 359 367 373 379 383 389 397 401 409 419 421 431
 433 439 443 449 457 461 463 467 479 487 491 499
 503 509 521 523 541 547 557 563 569 571 577 587
 593 599 601 607 613 617 619 631 641 643 647 653
 659 661 673 677 683 691 701 709 719 727 733 739
 743 751 757 761 769 773 787 797 809 811 821 823
 827 829 839 853 857 859 863 877 881 883 887
Program terminated

Вот мой вывод: 

Program initiated
   1  37  41  43  47  53  59  61  67  71  73  79
  83  89  97 101 103 107 109 113 127 131 137 139
 149 151 157 163 167 173 179 181 191 193 197 199
 211 223 227 229 233 239 241 251 257 263 269 271
 277 281 283 293 307 311 313 317 331 337 347 349
 353 359 367 373 379 383 389 397 401 409 419 421
 431 433 439 443 449 457 461 463 467 479 487 491
 499 503 509 521 523 541 547 557 563 569 571 577
 587 593 599 601 607 613 617 619 631 641 643 647
 653 659 661 673 677 683 691 701 709 719 727 733
 739 743 751 757 761 769 773 787 797 809 811 821
 823 827 829 839 853 857 859 863 877 881 883 887
Program terminated

Вот мой код: 

#include <stdio.h>

void zap(int data[], int divisor)
{
    for(int i=0;i<900;i++)
    {
        if(data[i]%divisor==0) // if mod is not 0, 0 out the index. 
        {
            data[i] = 0; 
        }
    }
}
// the display method 
void display(int data[])
{
    int count = 0; // init counter on the out side
    for(int i=0;i<900;i++)
    {
        if(data[i]>0)// don't print 0s
        {
            printf("%4d",data[i]);// print the data in a column 

            count++;// increment count 

            if(count==12) // print rows and columns 
            {
                count=0; // reset count
                printf("\n"); // print new line 
            }
        }
    }
    if(count<12)// we terminate loop and we now need print a new line 
    {
        printf("\n"); 
    }
}

int main()
{   
    // start the program, with a message
    printf("Program initiated\n"); 

    // needs to be 900 long 
    int primes[900];

    // populate the array 
    for(int i=1; i <= 900; i++)
    {
            primes[i] = i; 
    }

    // elminate the bad numbers 
    for(int i=2; i < 35; i++)
    {
        zap(primes,i); 
    }

    // display the array. 
    display(primes);

    // print the end message    
    printf("Program terminated\n"); 

    return 0; 
}

Ответы [ 3 ]

3 голосов
/ 19 марта 2012

Ваша функция zap всегда сбрасывает входное значение. Например, когда вы вызываете zap с делителем 2, он проверит 2%2, найдет 0 и уберет его, даже если 2 простое.

Чтобы это исправить, вы должны начать с divisor+1.

Но я замечаю, что на самом деле это вообще не сито. zap не должен выполнять какой-либо модуль, просто пройдитесь по массиву с шагом divisor. Дважды проверьте, что на самом деле представляет собой Сито Эратосфена.

2 голосов
/ 19 марта 2012

Это на самом деле не сито Эратосфена.Смысл этого алгоритма состоит в том, чтобы вообще не проверять делимость (с %) на вслепую (т.е. без каких-либо вычислений), исключая каждое 2-е число, кроме 2, затем каждое 3-е, кроме 3, затем каждое 4-е, кроме 4и т. д.

Вам необходимо исправить функцию zap: во-первых, не удаляйте число, если оно равно divisor, и не проверяйте остаток, просто удаляйте числа.

1 голос
/ 19 марта 2012

ну, вы можете использовать что-то вроде этого:

(инициализировать sieve как достаточно большой bool-массив с каждой записью, установленной в true - так как я хочу, чтобы это было просто установлено sieve[0] = false; sieve[1] = false;

for(int i = 2; i < endOfNumbers; i++)
{
   if (sieve[i] == false) continue;
   for (int m = 2*i; m < endOfNumbers; m += i)
      sieve[m]=false;
}
...