Thread: Feedback on prime number generator source code?

loop_count and i are basically doing the same job.

> for (int j = 2; j <= i/2; j++)
1. You only need to go up to the square root of i, not i/2
2. Start at 3, then do j += 2

But the presentation is otherwise very good.

Originally Posted by Salem

loop_count and i are basically doing the same job.

1. You only need to go up to the square root of i, not i/2

So they are. Missed that entirely during some recode.

Had to think about that second point for a hot minute. Great info to have. Is that because the factors are pairs? So you're actually eliminating the pair by only finding the lower factor?

--edit--

I may not be following your instructions correctly. Modded code is giving really odd false positives.

Code:

#include <stdio.h>
#include <math.h>

int main () {
        int loop_control = 0;
        int i = 2;

        printf("Program will verify if numbers are prime starting at 2. Number of times to loop: ");
        scanf(" %d", &loop_control);

        while (i < loop_control) {
                int isPrime = 1;

                for (int j = 3, k = sqrt(i); j <= k; j+=2) {
                        if (i % j == 0) {
                                isPrime = 0;
                                break;
                        }
                }

                if (isPrime == 1) {
                        printf("%d\n",i);
                }

                ++i;
        }

        return 0;
}

2, 3,4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 26, 28, 29, 31, 32, 34, 37 ...

Originally Posted by sepp

So you're actually eliminating the pair by only finding the lower factor?

More or less. If a is a factor of n, then n/a is also a factor. If a < sqrt(n) then n/a > sqrt(n).

Incidentally, look up "integer square root" for techniques to compute the square root of an integer without using floating point (which is inherently subject to numerical error).

As to your false positives: your approach tests for divisibility by odd factors. That won't work for testing even values.