Guest User

Prime Checker

a guest
Sep 9th, 2020
692
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from bisect import bisect_left
  2.  
  3. print('Generating 99,999 prime numbers... (Takes about 10 seconds)\n')
  4.  
  5. #-----------------------------------------------------------------------
  6.  
  7. def prime_list(n):
  8.     sieve = [True] * n
  9.     for i in xrange(3, int(n ** 0.5) + 1, 2):
  10.         if sieve[i]:
  11.             sieve[i * i::2 * i]=[False]*((n - i * i - 1) / (2 * i) + 1)
  12.     return [2] + [i for i in xrange(3, n, 2) if sieve[i]]
  13.  
  14. biggest_prime = 1299721 # The 100,001st prime
  15. second_to_biggest_prime = 1299709
  16. list_of_primes = prime_list(biggest_prime)
  17.  
  18. def take_closest(the_list, num):
  19.     pos = bisect_left(the_list, num)
  20.     if pos == 0:
  21.         return the_list[0]
  22.     if pos == len(the_list):
  23.         return the_list[-1]
  24.     before = the_list[pos - 1]
  25.     after = the_list[pos]
  26.     if after - num < num - before:
  27.         return after
  28.     else:
  29.         return before
  30.  
  31. def prime_info(num):
  32.  
  33.     if num == 1:
  34.         return 0, 2, 'None', 2      # 2 is the first prime, No previous prime, next prime is 2
  35.     if num == 2:
  36.         return 1, 3, 'None', 3
  37.  
  38.     number_of_prime = 0
  39.     nth_prime_number = 0
  40.     previous_prime = 0
  41.     next_prime = 0
  42.  
  43.     if num > 99999:
  44.         nth_prime_number = 'Unavailable'
  45.     else:
  46.         nth_prime_number = list_of_primes[num - 1]
  47.  
  48.     if num < second_to_biggest_prime:   # The last prime before the biggest_prime
  49.  
  50.         if num in list_of_primes:
  51.             number_of_prime = list_of_primes.index(num) + 1
  52.             previous_prime = list_of_primes[number_of_prime - 2]
  53.             next_prime = list_of_primes[number_of_prime]
  54.         else:
  55.  
  56.             prime = take_closest(list_of_primes, num)
  57.  
  58.             if num > prime:
  59.                 previous_prime = prime
  60.                 index = list_of_primes.index(previous_prime) + 1
  61.                 next_prime = list_of_primes[index]
  62.             else:
  63.                 next_prime = prime # Because the prime is greater than num
  64.                 index = list_of_primes.index(next_prime) - 1
  65.                 previous_prime = list_of_primes[index]
  66.  
  67.     else:
  68.  
  69.         previous_prime = 'Unavailable'
  70.         next_prime = 'Unavailable'
  71.  
  72.     return number_of_prime, nth_prime_number, previous_prime, next_prime
  73.  
  74. #-----------------------------------------------------------------------
  75.  
  76. for i in range(1, 1000):
  77.     prime_num, nth_prime, previous_prime, next_prime = prime_info(i)
  78.  
  79.     print('\n\nNumber: ' + str(i))
  80.     print('Prime #' + str(i) + ' is ' + str(nth_prime))
  81.  
  82.     the_nth_prime = nth_prime
  83.     two_sum = i + nth_prime
  84.  
  85.     print('The sum of these two numbers is ' + str(two_sum))
  86.  
  87.     prime_num, nth_prime, previous_prime, next_prime = prime_info(two_sum)
  88.  
  89.     if str(nth_prime) == 'Unavailable': exit()
  90.  
  91.     print('Prime #' + str(two_sum) + ' is ' + str(nth_prime))
  92.  
  93.     answer = nth_prime
  94.  
  95.     if len(str(answer)) > len(str(two_sum)):
  96.         shortened = str(answer)[:len(str(two_sum))]
  97.  
  98.         if shortened == str(the_nth_prime):
  99.             raw_input('                 Yes! ' + str(i) + ' self resolves!')
  100.  
  101. # The results for this program are 261, 262, and 263
RAW Paste Data