patterncppMinor

Generating prime numbers within a range in C++

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

rangenumberswithingeneratingprime

Problem

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
#include

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;i1)
            {
                holder[length++]=i;
            }
            else
            {
                length=0;
            }
        }
        count=0;
    }   

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

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

main

int main()
{
    int a,b;

    cout>a;

    cout>b;

    prime_gen(a,b);
}

Solution

Stylistic notes:

Use more spaces around punctuation (for(int i=0;i




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 = a) break;
}
return length - j;

Code Snippets

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

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;
    }
}

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

Context

StackExchange Code Review Q#5996, answer score: 6

Revisions (0)

No revisions yet.