Algorithm for Finding Primes

Using brute force isn’t particularly the best solution when it comes to determining primes.

Brute Force Example:

#number = int(input())


def isprime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    for i in range(n):
        if i <= 1:
            continue
        if i*i > n:
            return True
        if n % i == 0:
            return False


a = []
for i in range(100000):
    i += 1
    if isprime(i):
        a.append(i)
print(a)

Sieve of Eratosthenes: This method tries all the numbers, but as soon as a prime number is found all the multiples of it is marked as not prime, meaning there are less options to test. Here is a python example code.

def sieve_of_eratosthenes(n):
    primes = []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            primes.append(p)
            for i in range(p * p, n + 1, p):
                is_prime[i] = False

    for p in range(int(n**0.5) + 1, n + 1):
        if is_prime[p]:
            primes.append(p)

    return primes

limit = 100000
prime_numbers = sieve_of_eratosthenes(limit)
print(prime_numbers)