Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # FIRST I CREATE MY LIST. IN THIS LIST WE WILL HAVE SURE UP TO 10.000 PRIMES
- wantedList = list()
- # Finding the primes
- def findPrimes(LIMIT):
- primes = list()
- primes.append(2)
- for n in range(3, LIMIT):
- flag = True
- for i in range(len(primes)):
- if n % primes[i] == 0:
- flag = False
- break
- if flag == True:
- primes.append(n)
- return primes
- # First, we have to find the appearance frequency of a prime in a given LIMIT
- from matplotlib import pyplot as plt
- from timeit import default_timer as timer
- LIMITEXPONENTS = list(range(1, 7))
- times = list()
- numOfPrimes = list()
- for i in LIMITEXPONENTS:
- LIMIT = 10**i
- if LIMIT != 10**6:
- start = timer()
- primesI = findPrimes(LIMIT)
- end = timer()
- times.append(1000 * (end - start))
- numOfPrimes.append(len(primesI))
- else:
- start = timer()
- wantedList = findPrimes(LIMIT)
- end = timer()
- times.append(1000 * (end - start))
- numOfPrimes.append(len(wantedList))
- '''
- Above I made the same thing in if and else cases, with only one difference
- In the first 6 loops, the list is named primesI and this is a local variable
- In the last loop (LIMIT = 10^7), the list with primes is the global variable named "wantedList"
- 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
- '''
- # Now, we have a list named times, which calculates the time to find all the primes until a given LIMIT
- # Also, we created a list which contains the number of prime numbers until this given limit
- for i in LIMITEXPONENTS:
- LIMIT = 10**i
- frequency = LIMIT / numOfPrimes[i-1]
- frequency = int(100 * frequency) / 100
- print("1 until " + str(LIMIT) + ": There are " + str(numOfPrimes[i-1]) + " primes with frequency = " + str(frequency) + ". Execution time = " + str(times[i-1]) + " ms.")
- print(wantedList[10000])
- # Now , we know the frequencies:
- # Until 10 -----------> 2.5
- # Until 100 -----------> 4
- # Until 1000 ----------> 6
- # Until 10000 ---------> 8
- # Until 100000 --------> 10.5, we suppose it
- # Until 1000000 -------> 13, we suppose it
- # So, until 10000 there are about 1250 primes (exactly 1229)
- # So, until 100000 there are about 10000 primes (less than 10000 because frequency > 10, exactly 9592)
- # So, the 10.001st prime is between 10^6 and 10^7 and much closer to 10^6
- # time(100) = 10 * time(10)
- # time(1000) = 25 * time(100)
- # time(10000) = 45 * time(1000)
- # time(100000) = 90 * time(10000)
- # time(1000000) = 180 * time(100000) -----> WE SUPPOSE THAT, THE PREVIOUS ARE MY MEASUREMENTS
- # So, time(1000000) is about 25 minutes.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement