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

Question

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

That `continue` only skips the `for (j=i; j>i*i; j--)` loop's (non-existing) other code. — CoderCharmander, Jan 10 '20 at 20:23
https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — Yunnosch, Jan 10 '20 at 20:27
@CoderCharmander tried putting the 'prime[i] = i;' inside the 'for (j=i; j>i*i; j--)' however all i get as output is 0s. — Πάνος Ρεβολίδης, Jan 10 '20 at 20:29
The programmer's secret weapon is the debugger. With the debugger you can run the program at a rate the human mind can handle and inspect the many variables involved. For a small program like this you can step through the program line by line looking for where the program does something you don't expect. The unexpected is usually a bug. — user4581301, Jan 10 '20 at 20:31

score 1 · Answer 1 · answered Jan 10 '20 at 20:33

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

also no point in testing divisibility of e.g. 23 by 5,7,11,13 and 19. (or [testing divisibility at all](https://stackoverflow.com/questions/8302267/optimizing-prime-numbers-code/9435507#9435507), if one so chooses, but that's another matter entirely). :) — Will Ness, Jan 11 '20 at 05:54
just to restate that this code is needlessly quadratic. the loop condition `j < primecount` must be augmented to stop when the square of `j`th prime exceeds `i`. — Will Ness, Jun 25 '21 at 13:25

score 0 · Accepted Answer · answered Jan 11 '20 at 06:40

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.

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

2 Answers2