Advertisement
makispaiktis

Project Euler 35 - Count time for 2 different algorithms

May 18th, 2020 (edited)
1,038
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.44 KB | None | 0 0
  1. '''
  2. The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
  3. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
  4. How many circular primes are there below one million?
  5. '''
  6. from math import ceil, pow
  7.  
  8. # First, I create a list with all the primes
  9. LIMIT = list(int(pow(10, i)) for i in range(1, 5))
  10. def f1(LIMIT):
  11.     primes = [2]
  12.     for i in range(3, LIMIT):
  13.         isIPrime = True
  14.         for prime in primes:
  15.             if i % prime == 0:
  16.                 isIPrime = False
  17.                 break
  18.         if isIPrime == True:
  19.             primes.append(i)
  20.     return primes
  21.  
  22. def f2(LIMIT):
  23.     primes = [2]
  24.     for i in range(3, LIMIT):
  25.         isIPrime = True
  26.         for j in range(2, ceil(i/2+1)):
  27.             if i % j == 0:
  28.                 isIPrime = False
  29.         if isIPrime == True:
  30.             primes.append(i)
  31.     return primes
  32.  
  33. print(LIMIT)
  34. from timeit import default_timer as timer
  35. times1 = []
  36. times2 = []
  37. for limit in LIMIT:
  38.     start = timer()
  39.     f1(limit)
  40.     end = timer()
  41.     times1.append((end - start) * 1000)
  42.  
  43. for limit in LIMIT:
  44.     start = timer()
  45.     f2(limit)
  46.     end = timer()
  47.     times2.append((end - start) * 1000)
  48.  
  49. print("Limit      1st Function                   2nd Function")
  50. for i in range(len(LIMIT)):
  51.     print(str(LIMIT[i]) + "         " + str(times1[i]) + "       " + str(times2[i]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement