Sieve of Eratosthenes


#1



Hi guys, im still new so i dont know how does this work to solve the following question.
Why is there a need for it to square root?


"""By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?"""

def is_prime(x):
    div_by = [i for i in range(2, int(x ** 0.5) + 1)]
    for i in div_by:
        if x % i == 0:
            break
    else:
        return True

primes = []
test = 2
while True:
    if is_prime(test):
        primes.append(test)
    if len(primes) == 10001:
        break
    test += 1

print('prime list check:', primes[:10])
print('the number of primes found:', len(primes))
print('the 10001st prime:', primes[10000])


#2

For any given number, say 42, it will have factor pairs, like this:

1 * 42
2 * 21
3 * 14
6 * 7

Note that the square root of 42 is 6.48 and there are 4 factors of 42 before that square root (1, 2 ,3, 6) before it and 4 factors (42, 21, 14, 7) after it. It follows from the example and (from number theory calculations) that if a number has no factor (apart from 1) before its square root, it will have no factor (apart from itself) after the square root as well.

Thus, checking for factors till the square root is sufficient. Hope it helps! :slight_smile: