So from the tutorials I've been following this is code to find the prime numbers between 3 and 100 using array. What is the logic behind the p / primes[i] >= primes[i] condition in the second for loop?

For example if I follow the loop taking p = 5 and apply the condition it'll be 5 / primes[1] >= primes[1]:

Since we know primes[1] = 3 this will become 5 / 3 >= 3 which immediately becomes false. there should be a test to ensure the value of p does not exceed the sq root of primes[i] but here p / primes[i] >= primes[i] there is sq root of primes[i]

enter code here



int primes[50] = { 0 };
int primeIndex = 2;

bool isPrime;

// hardcode prime numbers
primes[0] = 2;
primes[1] = 3;

for (p = 5; p <= 100; p = p   2)
{
    isPrime = true;

    for (i = 1; isPrime && p / primes[i] >= primes[i];   i)
        if (p % primes[i] == 0)
            isPrime = false;

    if (isPrime == true)
    {
        primes[primeIndex] = p;
          primeIndex;
    }
}

for (i = 0;  i < primeIndex;    i)
     printf("%i  ", primes[i]);

printf("\n");
return 0;

}

CodePudding user response：

The logic is that:

1. In every pair of factors (m_1, m_2), either m_1 <= m_2 or m_2 <= m_1
2. If a number n has a multiplicative factor m_1, it also has a factor m_2 = n / m_1. So factors are actually paired: m with n/m.
3. Due to (1. 2.), if m is a factor n such that m > n/m, then n/m must also be a factor of n such that (n/m) <= n/(n/m) .

So it's enough to search for the "small" factors, to verify there are no larger ones.

CodePudding user response：

... there should be a test to ensure the value of p does not exceed the sq root of primes[i] ...

No. It is the other way around: "test to ensure the value of primes[i] does not exceed the sq root of p"

Or: "test to ensure the value of primes[i] squared does not exceed p".

Only iterate to √p

To only iterate to the root of p, instead of p / primes[i] >= primes[i], code could consider the similar:

p >= sqrt(primes[i])
// or 
p >= primes[i] * primes[i]

• sqrt(primes[i]) brings in floating point math. sqrt() is not specified to be exact, just close. FP math is also expensive compared to integer math. When using long long, more rounding woes occur.

• primes[i] * primes[i] risks overflow and undefined behavior when p is near INT_MAX.

• p / primes[i] >= primes[i] (or preferably as primes[i] <= p / primes[i]) has neither problem. Its computation costs may be scant as a good compiler will see the next p % primes[i] and perform both calculations for about the cost of one.