All the following algorithms produce a list of all primes less than n Question W
ID: 3889973 • Letter: A
Question
All the following algorithms produce a list of all primes less than n Question Which of the following algorithm is the fastest? EXPLAIN WHY Algorithm 1: Method1(n)l1 start with a boolean array, arrl, of size n, with all entries set to true now set each arrl [j] to false, if it is a multiple of 2 (and not 2). Next set arr1 [j] to false, if it is a multiple of 3 (and not 3), We see that arr1 [4] is false so we skip it. We see that arr1 [5] is true, so we set arr1 [j] to false, if it is a multiple of 5 (and not 5). We stop when we know that we have only arr1 [i] true, ifj is a prime Finally, copy all j such that arr1 =true into an ArrayList and return it Algorithm 2: Method2(n^ This time, start with an empty ArrayList, Loop through 2 to n-1: check that none of the current members of ArrayList divides i if none do, then add i to ArrayList Finally return list. Algorithm 3: Method3(n)l1 fill ArrayList with numbers 2, 3,... n-1 remove multiples of ArrayList[0] from ArrayList [1:] (this removes all multiples of 2 from ArrayList, leaving 2 in ArrayList) remove multiples of ArrayList [1] from ArrayList [2:] (this removes all multiples of 3 from ArrayList, leaving 3 in ArrayList) remove multiples of ArrayList [2] from ArrayList [3] (this removes all multiples of 5 from ArrayList, leaving 5 in ArrayList) finally return whatsleft of ArrayList Algorithm 4: Returns an ArrayList of primes less than n by checking whether each of 2,3, 4,...n-1 is primeExplanation / Answer
Algorithm 3 is the fastest of all the above algorithms. The name of this famous algorithm is Sieve of Eratosthenes.
Its time complexity is O(n). The most repetitive part of testing each element whether it is divisible by all the numbers less than it can be eliminated by implementing a simple division of particular number from 1 to n for each iteration. So for every iteration, each number gets eliminated and the no of elements after the every iteration become lesser and lesser. After the last iteration the numbers which were not eliminated i.e divisible remain.