#! python # -*- coding: utf-8 -*- """ Lab #5. @date: Mon Feb 02 09:29:51 2015. @author: Lilian Besson for CS101 course at Mahindra Ecole Centrale 2015. @licence: GNU Public License version 3. """ # %% Exercise 1 : print the n first odd numbers (from Prof. Dhande homework, Pb 5) n = int(raw_input("n = ? ")) k = 1 while k < 2*n: print k k += 2 # %% Exercise 2 : compute the first n first triangular numbers t_n = n*(n+1)/2 n = int(raw_input("n = ? ")) for i in xrange(1, n): print int(i*(i+1) / 2.0) # %% Exercise 3 : compute an approximation of pi**2/6 by the series studied in MA101 Final Exam # pi**2 / 6 = lim_(N --> +oo) sum_1^N 1/i**2 N = int(raw_input("Size of the partial sum N = ? ")) partial_sum = 0 for n in xrange(1, N): partial_sum += 1.0 / (n**2) approx = partial_sum print "With", N, "terms in the partial sum, pi**2/6 is computated as", approx # Check that it is not too bad: import math exact = math.pi**2 / 6.0 difference = abs(exact - approx) print "Difference between exact value and our approximation is", difference print "And relative difference between exact value and our approximation is", 100*difference/exact, "%." # %% Exercise 4 : with the example of numerical method given by Prof. Arya in the first lecture, compute an approximate value for square root of 2. # This method has also been studied in the chapter on sequences during MA101 k = 2.0 # goal N = int(raw_input("For the Babylonian method to approximate {}, the number of iteration is N = ".format(k))) x = k for n in xrange(N): print "For the", n, "th step, x =", x x = (x + k/x) / 2.0 # Cf your MA101 tutorial sheet from september approx = x print "With {} steps of the iterative method, sqrt({}) is computated as x = {}.".format(N, k, approx) print "And we can check that abs(x**2 - {}) = {} is not too big :) !".format(k, abs(x**2 - k)) # Check that it is not too bad: from math import sqrt exact = sqrt(k) difference = abs(exact - approx) print "Difference between exact value and our approximation is {}...".format(difference) print "And relative difference between exact value and our approximation is {:.3f} % : good job !".format(100*difference/exact) # %% Bonus for Exercise 4, do not ask the number of steps to the user, but a precision threshold from which we will stop. # The method will run as long as |x_n - x_n+1| >= epsilon k = 2.0 # goal digits = 7 digits = int(raw_input("For the Babylonian method to approximate {}, the precision threshold is digits = ".format(k))) epsilon = 10 ** (-digits) xnew = k x = -1 n = 1 while abs(x-xnew) >= epsilon: x = xnew print "For the", n, "th step, x =", x # Cf your MA101 tutorial sheet from september xnew = 0.5 * (x + k/x) n += 1 approx = x print "With a precision up-to {} digits, sqrt(2) is computated as x = {}".format(digits, approx) print "And we can check that abs(x**2 - {}) = {} is not too big :) !".format(k, abs(x**2 - k)) # Check that it is not too bad: from math import sqrt exact = sqrt(k) difference = abs(exact - approx) print "Difference between exact value and our approximation is {}...".format(difference) print "And relative difference between exact value and our approximation is {:.3f} % : well done !".format(100*difference/exact) # %% Bonus for problem 4 : adapt the method to compute the sqrt of any number # Write a function mysqrt that works return a good approximate value of the sqrt. def mysqrt(k = 2, digits = 2): """ Compute an approximation of the sqrt of k, by the Babylonian method, with an ensured precision of [digits] number of digits.""" assert type(digits) is int assert k > 0 assert digits > 0 epsilon = 10 ** (-digits) xnew = k x = -1 n = 1 # We want to be sure that the method always terminates ! while abs(x-xnew) >= epsilon and n < 1e8: x = xnew # print "For the", n, "th step, x =", x # Cf your MA101 tutorial sheet from september xnew = 0.5 * (x + k/x) n += 1 return x # Test it on some examples, integers or not integers from math import sqrt for k in [2, 4, 8.2344, 100]: print "\n\nFor k = {} :".format(k) for digits in [1, 2, 8]: approx = mysqrt(k, digits) exact = sqrt(k) print "\n For k = {} and digits = {}, mysqrt(k, digits) = {}.".format(k, digits, approx) difference = abs(exact - approx) print " With this threshold {}, relative difference between exact value and our approximation is {:.3f} % : well done !".format(digits, 100*difference/exact) # %% Exercise 5 : ask the user an input n, and check if n is a prime numer of not. n = input("n = ?") if n < 2: result = False else: result = True for k in xrange(2, int(math.sqrt(n))+1): if (n % k) == 0: # k is a divisor of n ==> n is not prime! result = False break # Exit the for loop RIGHT NOW! if result: print n, "is a prime number !" else: print n, "is NOT a prime number !" # %% Exercise 5 : print all the first 2015 prime numbers. # You should def isPrime(n): """ Check if n is a prime number Basic implementation with a for and if loops, and break construct.""" if n < 2: return False result = True for k in xrange(2, int(math.sqrt(n))+1): if (n % k) == 0: # k is a divisor of n ==> n is not prime! result = False break # Exit the for loop RIGHT NOW! return result nbprime = 2015 # Start it print "2 is the first prime number. Let's find the next", nbprime-1, "ones." i = 3 nb = 2 # As long as we do not have enough prime numbers while nb < nbprime: print i, "is the", nb, "th prime number." i += 2 while not(isPrime(i)): i += 2 nb += 1 print i, "is the last (the ", nb, "th one) prime number of our list." # %% One liner version, ugly # We use Pierre Dusart's formula for the upper bound # Reference: https://fr.wikipedia.org/wiki/Formules_pour_les_nombres_premiers#cite_note-3 import math;l=lambda p:math.log(p,2);x=xrange;print(lambda n:"\n".join(map(lambda (i,m):"The {}th prime number is {}.".format(i+1,m),enumerate(filter(lambda n:all(map(lambda k: ((n%k)!=0),x(2,int(1+n**.5)))),x(2,int(n*(l(n)+l(l(n))-.5))))[:n]))))(2015)