Competitive Python

Sieve of Eratosthenes is an algorithm that is used to generate all the primes up to a particular number . It is a very ancient algorithm but is very useful and also is a frequently seen in questions in competitive programming. This is a very elegant algorithm and is certainly better than trial division method . The idea behind this algorithm is to first select 2 and strike of all the multiples of because we know that they are composite. Then look for the next number that is not stricken off, it will definitely be a prime and then strike off all the multiples of that number. This goes on until the square of the number we select is greater than the limit that we assigned to it. As you will notice there is no need to go further because all of their multiple will already be stricken off by one or the other prime before it. To formalise the algorithm, it can be described as follows : Select the smallest prime from the list of all numbers upto n. Strike off all the multiples of the ...

A prime number is a number that is only divisible by 1 and the number itself. There are multiple ways we could test if a number is prime or not but today we will talk about two ways- Naive method sqrt(n) prime testing (the efficient method) The Naive method One method would be to check all possibilities from 2 to n - 1, n being the number we are testing. This would mean that if a number is prime we will have to search through all the numbers from 2 to n - 1. But if a number is not a prime then we will not have to search through all the possibilities, we will just return false if a number is completely divisible by another number that means it doesn't leave any remainder. def isPrime(n): for i in range(2,n): if n%i==0: return False return True The worst case for this method would be O(N). Sqrt(n) method Okay, so the logic behind this method is that every composite number has at least one factor that lies between 0 and the square root of n. ...