Advertisement
makispaiktis

Project Euler 7 - 10001st prime

Jul 23rd, 2020 (edited)
917
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.73 KB | None | 0 0
  1. # FIRST I CREATE MY LIST. IN THIS LIST WE WILL HAVE SURE UP TO 10.000 PRIMES
  2. wantedList = list()
  3.  
  4. # Finding the primes
  5. def findPrimes(LIMIT):
  6.     primes = list()
  7.     primes.append(2)
  8.     for n in range(3, LIMIT):
  9.         flag = True
  10.         for i in range(len(primes)):
  11.             if n % primes[i] == 0:
  12.                 flag = False
  13.                 break
  14.         if flag == True:
  15.             primes.append(n)
  16.     return primes
  17.  
  18. # First, we have to find the appearance frequency of a prime in a given LIMIT
  19. from matplotlib import pyplot as plt
  20. from timeit import default_timer as timer
  21.  
  22. LIMITEXPONENTS = list(range(1, 7))
  23. times = list()
  24. numOfPrimes = list()
  25. for i in LIMITEXPONENTS:
  26.     LIMIT = 10**i
  27.     if LIMIT != 10**6:
  28.         start = timer()
  29.         primesI = findPrimes(LIMIT)
  30.         end = timer()
  31.         times.append(1000 * (end - start))
  32.         numOfPrimes.append(len(primesI))
  33.     else:
  34.         start = timer()
  35.         wantedList = findPrimes(LIMIT)
  36.         end = timer()
  37.         times.append(1000 * (end - start))
  38.         numOfPrimes.append(len(wantedList))
  39.  
  40. '''
  41. Above I made the same thing in if and else cases, with only one difference
  42. In the first 6 loops, the list is named primesI and this is a local variable
  43. In the last loop (LIMIT = 10^7), the list with primes is the global variable named "wantedList"
  44. We have to do this, because I want to print the 10.001st prime, which I have proved is between 10^5 and 10^6, so when LIMIT = 10^6
  45. '''
  46.  
  47. # Now, we have a list named times, which calculates the time to find all the primes until a given LIMIT
  48. # Also, we created a list which contains the number of prime numbers until this given limit
  49. for i in LIMITEXPONENTS:
  50.     LIMIT = 10**i
  51.     frequency = LIMIT / numOfPrimes[i-1]
  52.     frequency = int(100 * frequency) / 100
  53.     print("1 until " + str(LIMIT) + ": There are " + str(numOfPrimes[i-1]) + " primes with frequency = " + str(frequency) + ".    Execution time = " + str(times[i-1]) + " ms.")
  54.  
  55. print(wantedList[10000])
  56.  
  57. # Now , we know the frequencies:
  58. # Until 10  -----------> 2.5
  59. # Until 100 -----------> 4
  60. # Until 1000 ----------> 6
  61. # Until 10000 ---------> 8
  62. # Until 100000 --------> 10.5, we suppose it
  63. # Until 1000000 -------> 13, we suppose it
  64.  
  65. # So, until 10000  there are about 1250 primes (exactly 1229)
  66. # So, until 100000 there are about 10000 primes (less than 10000 because frequency > 10, exactly 9592)
  67. # So, the 10.001st prime is between 10^6 and 10^7 and much closer to 10^6
  68.  
  69. # time(100) = 10 * time(10)
  70. # time(1000) = 25 * time(100)
  71. # time(10000) = 45 * time(1000)
  72. # time(100000) = 90 * time(10000)
  73. # time(1000000) = 180 * time(100000) -----> WE SUPPOSE THAT, THE PREVIOUS ARE MY MEASUREMENTS
  74. # So, time(1000000) is about 25 minutes.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement