The average-case efficiency of Euclids algorithm on inputs of size n can be measured by the average number of divisions Davg(n) made by the algorithm in computing gcd(n, 1), gcd(n, 2), . . . , gcd(n, n). For example, Davg(5) = 1/5 (1 + 2 + 3 + 2 + 1) = 1.8.

Produce a scatterplot of Davg(n) and indicate the algorithms likely average case efficiency class.

Please practice your R language skills by programming sieve of erastosthenes algorithm.