Почему моя программа выдает мне все непростые числа, когда я прошу простые числа?

Я хочу использовать битовый массив и алгоритм сита Эратосфена, чтобы найти все простые числа в определенном диапазоне. Мой код компилируется, но он печатает все непростые числа, а не простые числа (кроме 2, потому что я прошу свою функцию Sieve напечатать 2). Может ли кто-нибудь просмотреть мой код и подсказать, как это исправить? Ваша помощь очень ценится. Спасибо!

Примечание. Моя домашняя работа требует использования битового массива.

#include <stdio.h>
#include <stdlib.h>

//#define MAXBYTES 1000000
#define MAXBYTES 10


void setBit(unsigned int A[], int k);
unsigned getBit(unsigned int A[], int k);
void print_prime (int prime_num);
void sieve_Prime(unsigned int bit_arr[]);

int main (int argc, char** argv)
{
    //int bit_arr[MAXBYTES];      //This is the bit array (32 X MAXBYTES)
    unsigned int bit_arr[MAXBYTES];      //or bit_arr[MAXBYTES]
    int i;

    for (i=0; i < MAXBYTES; i++)
    {
        bit_arr[i] = 0x00;            //initialize all bits to 0s
    }

    setBit(bit_arr, 0);             //0 is not prime, set it to be 1
    setBit(bit_arr, 1);             //1 is not prime, set it to be 1

    sieve_Prime(bit_arr);
    printf("\n");

    return 0;

}

//Set the bit at the k-th position to 1
void setBit(unsigned int A[], int k)
{
    int i = k/32;
    int pos = k % 32;

    unsigned int flag = 1;      //flag = 0000 ..... 00001
    flag = flag << pos;         //flag = 0000...010...000 (shifted k positions)

    A[i] = A[i] | flag;         //Set the bit at the k-th position in A[i];
}

//get the bit at the k-th position
unsigned getBit(unsigned int A[], int k)
{
    int i =k/32;
    int pos = k % 32;

    unsigned int flag = 1;

    flag = flag << pos;

    if (A[i] & flag)
        return 1;
    else
        return 0;
}


void print_prime (int prime_num)
{
    //print a prime number in next of 8 columns
    static int numfound=0;

    if (numfound % 8 == 0)
        printf("\n");
    if (prime_num+1 < MAXBYTES*8)
        printf("%d\t", prime_num);
    numfound++;
}

void sieve_Prime(unsigned int bit_arr[])
{
    int i;
    int k;
    int next_prime = 2;

    print_prime(2);

    while (next_prime+1 < MAXBYTES*8)
    {
        k = next_prime;

        //multiples of next_prime is not primpe
        while(next_prime*k < MAXBYTES*8)
        {
            setBit(bit_arr, next_prime*k);      //set it to be 1
            k++;     
        }

        //find next_prime by skipping non-prime bits marked 1
        while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, ++next_prime))
        {
            print_prime(next_prime);
        }
    }
}

c primes sieve-of-eratosthenes
person user2203774    schedule 17.08.2013    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Проблема в вашем цикле:

while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, ++next_prime))
{
    print_prime(next_prime);
}

Вы продолжаете печатать пока бит установлен (т.е. пока вы знаете, что это не простое число). По сути, ваш цикл - это «распечатать все числа, которые я нахожу при поиске следующего простого числа», а не «искать следующее простое число в цикле, а затем печатать следующее простое число».

Я подозреваю, что вам нужно что-то вроде:

next_prime++; // We always want to at least move on once...
while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, next_prime))
{
    next_prime++;
}
print_prime(next_prime);

Я не проверял, все что-то было не так с кодом, но это определенно первое, что нужно исправить.

person Jon Skeet    schedule 17.08.2013
comment
Спасибо за совет. Я попробовал ваше предложение, не сработало. Я получаю кучу 2сек. Есть другие предложения? - person user2203774; 17.08.2013
comment
@ user2203774: Вы пробовали отладку через это? Вам нужно научиться диагностировать проблемы. Вполне возможно, что вам понадобится один безусловный next_prime++; перед циклом - отредактирую это в моем ответе. - person Jon Skeet; 17.08.2013
comment
Спасибо. Я новичок в программировании. Я хочу узнать больше об отладке. Я буду смотреть в него. - person user2203774; 17.08.2013

arrow_upward
0
arrow_downward

Вы можете инициализировать массив с нулевыми значениями, просто добавив следующую конструкцию инициализации:

unsigned int bit_arr[MAXBYTES] = { };

Тогда каждый член массива будет содержать нулевое значение. Также старайтесь избегать таких вещей, как printf("\n");. Лучше использовать putchar('\n'), если вам нужно выводить только один символ за раз.

Кроме того, вы можете добавить ключевое слово static в прототипы и определения ваших рабочих функций, за исключением функции main, если вы не будете использовать эти подпрограммы вне этой единицы трансляции.

person mesmerizingr    schedule 17.08.2013