Sieve of Eratosthenes

#   Hello, today i want to tell you some informantion about prime numbers
#   and algoritms, which help to work with faster and easier.
#   Prime number is number, whose divisors are 1 and the number itself.

#   So, lets code a function, which will return all prime numbers in range from 1 to N.

def isPrime(n):
  allPrimes = []

  for k in range(2, n+1):
    prime = True
    for i in range(2, k):
        if k%i == 0:
            prime = False
            break

    if prime:
        allPrimes.append(k)
  return allPrimes

#   The asymptotic complexity of this algorithm is O(N^2)

#   The asymptotic complexity of an algorithm is a method for estimating the computational complexity
#   of an algorithm "up to a constant", used in complexity theory.



#   This algorithm is very slow. Why? Because when N will be more then 10^6 it will work for 10-15 secs.
#   We dont have this time, thats why I would like to show you The Eieve of Eratosthen.

#   The idea of this algo is very easy:
#   We will write down a series of numbers 1...n, and we will first cross out all the numbers divisible by 2,
#   except for the number 2 itself, then divisible by 3, except for the number 3 itself, then by 5,
#   then by 7, 11, and all the other primes up to n.

#   So, lets code =)

def eratosthenes(N):
    a = [i for i in range(1, N+1)] #    there would be prime numbes
    b = [] #    there would be crossed
    num=2   #   prime numbers, which will be checkes, so 2, 3, 5...
    i=0 #   counter
    a.remove(1) #   1 - not prime numbee

    while num < a[-1]: #    while num is less than the last number in list a
        while len(a) > i:   #   while as long as the length of a is greater than i, that is, it is a
                            # loop that goes through the list looking for numbers that are multiples of num and deletes them
            if a[i]%num == 0 and a[i]!= num:    # if the remainder of the number in the list at position i is zero ,
                                                # we add it to the deleted list(b) and delete it from a
                b.append(a[i]) #    adding
                a.pop(i) #  deleting
            i+=1 #  check the next position
        i=0 #   resetting the counter

        # next num
        for j in range(len(a)):
            if a[j] > num:
                num = a[j]
                break

    return b

#   The asymptotic complexity of this algorithm is O(N*log(log(n))), So you can find a prime fast =)