James Zhou 2000

finding prime numbers

the other day, I found some discussions about finding prime numbers. I did a quick search on google. Most of the codes that show up are similar to the brute force search. Few take advantages of the fact that a non-prime number can always be represented a multiplication of its prime factors.

So I decided to write a C code. I think it might be more efficient if I avoid all the divisions or any multiplications if possible. I posted my code below. I choose a Boolean array to indicate whether an element is a prime or not. For example, if 7 is a prime, then numbers[7] = true;

The basic idea is:

1. initialize all flags with true status.
2. set the first prime (or first two if you want) number
3. loop until I find the next prime
4. using this prime as the step, loop again to set all its multiples to “false”
5. goto #3

//================== code begin ===================//

#define LEN (100)  // find all primes between 0 and 100
bool numbers[LEN];  // "true" means prime, false means not.
void one_pass_check(bool *list, int begin, int end);

int main()
{
    int i;
    for(i =0; i < LEN; i++)
        numbers[i] = true; //assuming all are prime numbers at first

    numbers[0] = false;  //0 is not a prime
    numbers[1] = false;  //1 is not a prime
    numbers[2] = true;  //2 is a prime
    numbers[3] = true;  //3 is a prime

    for (i = 0; i < LEN; i++)
    {
        if(false == numbers[i]) continue;
        printf("%d\n", i); // print out the current prime
        one_pass_check(numbers, i, LEN - 1); //set flags on all its multiples
    }
    return 0;
}

void one_pass_check(bool *list, int begin, int end)
{
    int i = begin + begin;
    for (; i<=end; i = i + begin)
    list[i] = false;
}


//================== code end ===================//

posted by jameszhou2000 @ 1:43 PM 0 comments