Logic behind p / primes[i] >= primes[i] while finding prime numbers using array

user_13412737 0
Viewed 145

So I am a beginner in C and while I have experience in python I can't wrap my brain around a simple problem.

Finding prime numbers in Python was a easier task if I remember but I am facing difficulties while doing the same in C.

So from the tutorials I've been following this is code to find the prime numbers between 3 and 100 using arrays:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main()
{
    int p;
    int i;

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

The first for loop in the above code was understandable but what happened after the second one is confusing me.

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.

Please explain what is happening after the first for loop

Edit: I have added the python code which I can do by myself. Why isn't it possible to do the same way in C:

lst = [2]
for i in range(3, 100):
     for j in range(2, i):
          if (i % j) == 0:
                break
     else:
          lst.append(i)

print(lst)
for-loop c arrays
1 Answers

The inner for loop tries all odd prime numbers found so far up to an including sqrt(p) without actually computing sqrt(p). The loop stops as soon as it finds a prime number that evenly divides p. It might be more readable as:

    isPrime = true;
    for (i = 1; p / primes[i] >= primes[i]; ++i) {
        if (p % primes[i] == 0) {
            isPrime = false;
            break;
        }
    }

In the case of 5, to loop does not start because 5 < 3*3, 5 is a prime number, same for 7: no test is needed to determine its primality.

Your python code is more elegant thanks to the else: clause of the for statement that executes only if the loop exits normally. Yet the algorithm in the python version is much less efficient as you test all numbers, including even ones and all divisors up to i. For 100, the difference is barely noticeable, but for much larger ranges, the added complexity will show. Also note that lst should be initialized as lst = [2] for the list of prime numbers to be correct, and you can remove the if i > 1: which is redundant.

user_45932670
Related