Myujth

Input: A number, max (a large number)
Output: All the primes from 1 to max
Output is in the form of a list and will be [2,3,5,7,11,13,.......]
The code attempts to perform this task in an efficient way (least time complexity).

from math import sqrt 
max = (10**6)*3
print("nThis code prints all primes till: " , max , "n")
list_primes=[2]

def am_i_prime(num):
 """
 Input/Parameter the function takes: An integer number
 Output: returns True, if the number is prime and False if not
 """ 
 decision=True
 i=0
 while(list_primes[i] <= sqrt(num)): #Till sqrt(n) to save comparisons
 if(num%list_primes[i]==0):
 decision=False
 break
 #break is inserted so that we get out of comparisons faster
 #Eg. for 1568, we should break from the loop as soon as we know that 1568%2==0
 i+=1
 return decision


for i in range(3,max,2): #starts from 3 as our list contains 2 from the beginning
 if am_i_prime(i)==True:
 list_primes.append(i) #if a number is found to be prime, we append it to our list of primes

print(list_primes)

How can I make this faster? Where can I improve?
What is the time complexity of this code? Which steps are inefficient?
In what ways is the Sieve of Eratosthenes more efficient than this?

Working for the first few iterations:-

1. We have a list_primes which contains prime numbers. It initially contains only 2.


2. We go to the next number, 3. Is 3 divisible by any of the numbers in list_primes? No! We append 3 to list_primes. Right now, list_primes=[2,3]


3. We go to the next number 4. Is 4 divisible by any of the numbers in list_primes? Yes (4 is divisible by 2). So, we don't do anything. Right now list_primes=[2,3]


4. We go to the next number, 5. Is 5 divisible by any of the numbers in list_primes? No! We append 5 to list_primes. Right now, list_primes=[2,3,5]


5. We go to the next number, 6. Is 6 divisible by any of the numbers in list_primes? Yes (6 is divisible by 2 and also divisible by 3). So, we don't do anything. Right now list_primes=[2,3,5]


6. And so on...

Interestingly, it takes a rather deep mathematical theorem to prove that your algorithm is correct at all. The theorem is: "For every n ≥ 2, there is a prime number between n and n^2". I know it has been proven, and much stricter bounds are proven, but I must admit I wouldn't know how to prove it myself. And if this theorem is not correct, then the loop in am_i_prime can go past the bounds of the array.

The number of primes ≤ k is O (k / log k) - this is again a very deep mathematical theorem. Again, beyond me to prove.

But anyway, there are about n / log n primes up to n, and for these primes the loop will iterate through all primes up to n^(1/2), and there are O (n^(1/2) / log n) of them.

So for the primes alone, the runtime is therefore O (n^1.5 / log^2 n), so that is a lower bound. With some effort it should be possible to prove that for all numbers, the runtime is asymptotically the same.

O (n^1.5 / log n) is obviously an upper bound, but experimentally the number of divisions to find all primes ≤ n seems to be ≤ 2 n^1.5 / log^2 n, where log is the natural logarithm.

O(N**2)

Approximately speaking, the first call to am_I_prime does 1 comparison, the second does 2, ..., so the total count is 1 + 2 + ... + N, which is (N * (N-1)) / 2, which has order N-squared.