PROBLEM LINKSAuthor:SRIKANT BADRIDIFFICULTY:SIMPLEPREREQUISITES:Concept of PrimePROBLEM:To find all prime numbers upto 10^7EXPLANATION:To gain 100 points one must know an efficient algorithm to evaluate prime numbers upto 10^7 in 1 sec. One such algorithm is Sieve Of Eratosthenes. The approach used by this algorithm is: Step 1:Create a bool arrray having size 10000000. Step 2:Initialize every value of that array with true & initialize index 0,1 as false since they are not primes. (You can use memset function in C,C++ for this) Step 3: Pick a number from bool array which is not false. Step 4: Make all multiples of that number in the array as false. Step 5: Repeat step 3 & 4 until all the elements (<=10000000) having true value have not been considered. Step 6: All the elements having true values are primes. The code for above algorithm is:
SAMPLE SOLUTION:Author asked 09 Oct '16, 21:58
