Generating prime numbers within a range in C++

Question

I was given a problem to find out all the prime numbers within a range. Just after I wrote the program I found numerous other codes to solve the problem. I am interested to know is my algorithm efficient? Is it like sieve filtration? (before writing this code I had no clear idea on sieve filtration method) or the algorithm I used is bad?

#include<iostream.h>
#include<math.h>

prime_gen

void prime_gen(int a,int b)
{
    int array[4]={2,3,5,7},holder[1000000]={0},count=0,flag=0,length=0,number_count=0;

    for(int i=0;i<b;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(i==array[j])
            {
                break;
            }
            else
            {
                if(i%array[j]==0)
                {
                    count++;
                }
            }
        }
        if(count==0)
        {
            if(i>1)
            {
                holder[length++]=i;
            }
            else
            {
                length=0;
            }
        }
        count=0;
    }   

    if(length==0)
    {   
        cout<<"No prime numbers exist within the range";
        cout<<"\n";
    }                               
    else 
    {                                                               
        cout<<"Prime numbers are:";

        for(int i=0;i<length;i++)
        {                                                                                   
            int t=holder[i];

            for(int check=0;check<sqrt(length);check++)
            {

                if(t!=holder[check])
                {
                    if(t%holder[check]==0)
                    {
                        t=0;
                    }
                }
            }

            if(t!=0&&t>=a)
            {
                number_count++;
                cout<<t<<"\t";
            }
        }

        cout<<"Total count:"<<number_count<<endl;
    }
}

main

int main()
{
    int a,b;

    cout<<"Put the first integer:";
    cin>>a;

    cout<<"Put the second integer:";
    cin>>b;

    prime_gen(a,b);
}

Answer 1

Stylistic notes:

• Use more spaces around punctuation (for(int i=0;i<b;i++) wants to breeze), don't sprinkle your code with blank lines in random places, and use consistent indentation.
• Declare your variables on separate lines; use the blank space on the right to write a comment explaining what the variable is for.
• Use meaningful variable names. Come on, array? The reader can see that it's an array, but what does it contain?

Also, make up your mind: you're writing C++, not C. Some parts (such as the use of C arrays) are not idiomatic C++ though; you should pick one, either C (and use stdio, not iostream) or C++ (and use new and the STL). Since I'm a C programmer but don't know much C++, I'm going to comment on the C-ish parts and not say anything about idiomatic C++.

The array variable isn't useful here. The small primes will appear in the holder array anyway, so put them in directly. Even if you were handling small primes specially, your count variable is useless: you don't need to count how many small primes divide i, you only need to know whether some small prime divides i.

Also, you might as well use unsigned integers for your variables, since they're not going to contain negative numbers.

unsigned holders[1000000]; /* list of prime numbers */
unsigned length = 0;
holders[length++] = 2;
holders[length++] = 3;
holders[length++] = 5;
holders[length++] = 7;

You do not need to fully initialize holders, since you'll be only looking at the first length elements. While you could write unsigned holders[1000000] = {3, 5, 7}; and the compiler would fill the rest with zeroes, with typical implementations, this would result in the full array (zeroes included) being written into your executable, which is a huge waste.

You should be allocating the holders dynamically anyway, and checking its size. If someone passes such a large value for b that the holders array overflows, your code will overwrite some arbitrary memory. Either compute the size of the holders array so that it's large enough given b, or keep track of its size and extend it if length becomes too large.

Even numbers are never prime. So instead of looping over all integers, loop over all odd integers.

There's no reason to fill holders with non-prime numbers. Your whole first loop can be eliminated.

for (x = 11; x < b; x += 2) {
    bool is_prime = true;
    // start j at 1.
    // As holders[0] is 2 and no value of x is divisible by 2.
    for (j = 1; j < length && holders[j] <= sqrt(x); j++) {
        if (x % holders[j] == 0) {
            is_prime = false;
            break;
        }
    }
    if (is_prime) {
        holders[length++] = x;
    }
}

Now, to find the number of primes between a and b, traverse the holders array from the first value that's larger or equal to a. When you write a complete program, take care of the boundary conditions; in particular, make sure to count 2 if a ≤ 2.

for (j = 0; j < length; j++) {
     if (holders[j] >= a) break;
}
return length - j;

Answer 2

Your code is not correct, hence its efficiency is irrelevant. You only test for divisibility by 2, 3, 5 and 7, so you would classify e.g. 121 = 11*11 as prime.

Answer 3

My version of the sieve is at http://ideone.com/1AP8u, and the function that does the sieving is shown below. Explanations are at my blog; look for "Prime Numbers" in the "Themes" tag under the "Exercises" menu bar item.

struct node* sieve(int n) {
    int m = (n-1) / 2;
    char b[m/8+1];
    int i=0;
    int p=3;
    struct node* ps = NULL;
    int j;

    ps = insert(2, ps);

    memset(b,255,sizeof(b));

    while (p*p<n) {
        if ISBITSET(b,i) {
            ps = insert(p, ps);
            j = 2*i*i + 6*i + 3;
            while (j < m) {
                CLEARBIT(b,j);
                j = j + i + i + 3; } }
        i+=1; p+=2; }

    while (i<m) {
        if ISBITSET(b,i) {
            ps = insert(p, ps); }
        i+=1; p+=2; }

    return reverse(ps); }

Answer 4

the "holder[1000000];" array lives on the stack ("is an automatic variable"). I would at least make it static, since it can be reused, and a lot of work went into it (that would involve sifting out the unsieved entries, but for a real program (and a function that is called more than once) it would be a win.