6
\$\begingroup\$

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);
}
\$\endgroup\$
6
\$\begingroup\$

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;
\$\endgroup\$
  • 1
    \$\begingroup\$ exactly these were the issues I was thinking about.Thanks \$\endgroup\$ – MiNdFrEaK Nov 13 '11 at 23:02
  • \$\begingroup\$ <quote>being written into your executable, which is a huge waste</quote> Because disk space is so costly? \$\endgroup\$ – Martin York Nov 14 '11 at 16:44
  • \$\begingroup\$ @LokiAstari Thanks. You're absolutely right about the misplaced insertion into holders. I prefer to skip odd numbers because it's a very simple optimization with a noticeable effect, but I've inserted 2 into the array to correctly handle the case when a≤2. \$\endgroup\$ – Gilles 'SO- stop being evil' Nov 14 '11 at 22:17
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think its corrected now \$\endgroup\$ – MiNdFrEaK Nov 13 '11 at 10:08
4
\$\begingroup\$

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); }
\$\endgroup\$
  • \$\begingroup\$ That's a nice implementation. Two things I've found useful, a) use 32 (or maybe 64) bit integers for your sieve, b) revert the bit logic, start with all zeros and set bits for composites to 1. Aligned reads and writes are generally much faster than accessing single bytes, and b[i>>w] |= 1 << (i&m); is one bit operation less per tick-off (although, that probably doesn't make a difference on modern processors anymore). \$\endgroup\$ – Daniel Fischer Nov 13 '11 at 3:35
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Generally,people use to loop upto maximum number(from input) or square root of it..I thought,what if they only needed to loop sqrt of the total number of already calculated superset of prime numbers which only contain the erroneous values(i.e the multiple of some other primes)..so,i did make a subset of nearly prime numbers from the set of all natural numbers,then sort out the pure primes by only looping through the sqrt of the numbers(here length)of the apparently not pure set of prime numbers.I kept them at an array to avoid calculating them each time on the fly. \$\endgroup\$ – MiNdFrEaK Nov 13 '11 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.