CODEWITHSUNDEEP
c++primes
Πάνος Ρεβολίδης
Πάνος Ρεβολίδης

Reputation: 15

How do I fix my Prime Generating program, from producing composite numbers

I am trying, to write a program in C++, that will calculate prime numbers, and store them in an array. Consider this is my third code.

The problem I have run into, is that, while I get Prime numbers, I also get composite numbers, specifically multiples of 5 and 7 (at least until the limit of 30). I know, the code will probably, be terrible, but it was, what I could come up with given my limited experience in both coding and prime numbers.

This is what I've written:

#include <iostream>
int j;
int i = 3;
int prime[30];

int main()
{
    for (i; i < 30; i+=2)
    {
        for (j =i; j>i*i; j--)
        {
            if ((i % j) == 0)
            {
                continue;
            }
        }
        prime[i] = i;
        std::cout << prime[i] << std::endl;
    }
}

output: 3 5 7 9 11 13 15 17 19 21 23 25 27 29

Upvotes: 1

Views: 82

Answers (2)

Will Ness
Will Ness

Reputation: 71099

As CoderCharmander points out in the comments, that continue only breaks from the inner loop but you intended to continue with the outer loop. Smallest fix is to use the dreaded goto, entirely appropriate here.

Also the inner for loop specification is all wrong:

#include <iostream>

int prime[30];

int main()
{
    int i, j;
    std::cout << 2 << " ";     // the first prime is 2
    for (i=3; i < 30; i+=2)
    {
        for // all wrong: (j =i; j>i*i; j--)
            (j = 2; j*j <= i; ++j)    // or even, (j = 3; j*j <= i; j += 2)
        {
            if ((i % j) == 0)
            {
                prime[i] = 0;  // initialize the non-primes as well!
                goto L1;       // continue the outer loop
            }
        }
        // the inner loop finished normally
        prime[i] = i;  
        std::cout << i << " ";

        L1: ;
    }
}

This also needlessly tests the numbers by all the numbers above 2 smaller than the threshold (or by the odds, as in the commented suggestion) but we only really need to test by primes.

When making this amendment it's important to be careful not to introduce the much bigger inefficiency than the one we were trying to fix (a quadratic loss in time complexity over an intended log factor gain), as there's no point in testing divisibility of e.g. 23 by 5,7,11,13 and 19.

And actually testing divisibility can be avoided altogether, if one so chooses, but that's another matter entirely.

Upvotes: 0

selbie
selbie

Reputation: 104559

Your inner loop only needs to test divisibility with the prime numbers you've encountered thus far. (e.g. no point in testing divisibility with 9 if you've already tested divisibility with 3)

int main()
{
    int j;
    int i = 3;
    int primes[30];
    int primecount = 0;

    primes[primecount++] = 2;  // hardcode 2, it's the only even number

    for (i = 3; i < 30; i += 2)
    {
        bool isPrime = true;

        for (j = 0; j < primecount; j++)
        {
            if ((i % primes[j]) == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes[primecount++] = i;
        }
    }

    for (int k = 0; k < primecount; k++)
    {
        std::cout << primes[k] << " ";
    }
    std::cout << std::endl;
}

Upvotes: 1

Related Questions