# -*- coding: utf-8 -*- """ Created on Sun Sep 27 15:57:16 2020 @author: jbobowsk """ # This function finds all of the prime numbers between integer inputs a and # b with b > a. The function returns an array of the prime numbers listed # in sequential order and an integer equal to the number of prime numbers # that exist between a and b. # Note that the syntax 'y % x' results in the remainder of y/x. Therefore, # 'y % 1' has a remainder of zero if and only if y is an integer. def primes_adv(a, b): piN = [] # Initialize an empty array if a % 1 == 0 and b % 1 == 0 and a > 0 and b > 0 and b > a: # This first # if statement checks to see if a and b are positive integers with # b > a. If any of the conditions fail, an error message is returned. import numpy as np import pandas as pd # with open('primes_list.txt', 'r') as f: # lineList = f.readlines() # with open("primes_list.txt", "ab") as f: # if len(lineList[-1].split('\n')) == 1: # f.write(b"\n") # The lines above (commented out) check to see if the last entry in primes_list.txt # is followed by an end of line indicator ("/n"). This is needed to ensure that the # format of the file is maintained as new prime numbers are added to the list. If # the end of line is missing, then the progam will add it before starting the search # from primes. If we can assume that the user is supplying a properly formatted # list of primes, we can omit the check. primeMax = int(np.loadtxt("primes_max.txt")) # Read in the largest prime found so far. primeNums = pd.read_csv("./primes_list.txt", delimiter="\n", header = None).values[:, 0] # Read the sequential list of primes into a list. I found that the 'pandas' module was # much faster than 'nupmy.loadtxt()'. if b <= primeMax: # % If b is less than primeMax, then there's no need to search, #just extract the needed the prime numbers from the list. i = 0 while i <= len(primeNums) - 1 and primeNums[i] <= b: if primeNums[i] >= a: piN = piN + [primeNums[i]] #% Add prime numbers to piN if the prime #is greater than or equal to 'a' and less than our equal to 'b'. i += 1 # Increment i by 1. Equivalent to i = i + 1 f = np.array(piN) # Convert the prime list to an array. n = len(f) # Get the total number of primes found. elif b > primeMax: # % If 'b' is larger than the largest previously found prime, # then we have to do some searching. for i in range(primeMax + 1, int(b) + 1): # % Start the search from at the # interger that is one greater than the largest prime number in our list # of known primes. Stop the search when we reach 'b'. cnt = 0 # Counter variable used to stop the while loop. if i != 1 and i % 2 == 1 and sum(map(int, str(i))) % 3 != 0\ and i % 10 != 5 or i == 2 or i == 3 or i == 5: # We only need to consider odd integers, # integers in which the sum of the digits of the number is not divisible by 3, # integers that are not divisible by 5, and the numbers 2, 3, and 5 (the first few primes). j = 3 # % Start from the fourth item is primes_list (2, 3, 5, 7) which is the number 7. # We don't have to check 2, 3, 5 because the if statement above has already done this. # Note that, this means prime_max.txt must be at least 7 and primes_list.txt must at # least contain 2, 3, 5, 7. while primeNums[j] < i/primeNums[j - 1] and cnt == 0: # % Execute the loop while primeNums[j] < i/primeNums[j - 1] and while cnt = 0 # (i.e. no factors of i have been found). # This is the line that makes this search more effieicent than that of 'primes()'. # First, it only checks if the known prime numbers are factors of i. # Second, it cuts off the search once primeNums[j] < i/primeNums[j - 1]. The reason # for dividing i by primeNums[j - 1] is the following: # If primeNums(j) is not a factor of i, then it's guaranteed that i will not have any # factors larger than i/primeNums[j - 1]. # Take 25, for example. j = 3 is not a factor of 25, so any number greater than # 25/3 = 8.33 cannot be a factor of 25. if i % primeNums[j] == 0: # Check if i/primeNums(j) has a remainder. If it doesn't, # then i is not prime and cnt set equal to one. cnt = 1 primeMax = i # Increase the value of the largest number checked for "primeness". j += 1 # Increment j for the next iteration of the while loop. if cnt == 0: # If the while loop completes and cnt = 0, then i is prime. primeMax = i # Increase the value of the largest number checked for "primeness". primeNums = np.append(primeNums, i) # Add i to the list of prime numbers. np.savetxt('primes_max.txt', np.array([primeMax]), fmt='%i', delimiter='\n') # Update primes_max.txt with open("primes_list.txt", "ab") as f: np.savetxt(f, np.array([i]), fmt='%i') # Update primes_list.txt else: primeMax = i # If it's not necessary to check if i is prime (i.e. i is even or a # factor of 3 or a factor of 5), then increase the value of the largest number # checked for "primeness". # np.savetxt('primes_max.txt', np.array([primeMax]), fmt='%i', delimiter='\n') # We could update primes_max.txt, but I commented out the line above to save time # (i.e. not necessary to constantly update primes_max.txt. np.savetxt('primes_max.txt', np.array([primeMax]), fmt='%i', delimiter='\n') # The search has ended, so update primes_max.txt. i = 0 while i <= len(primeNums) - 1 and primeNums[i] <= b: # Now that the search is done, # extract the needed the prime numbers from the updated list. if primeNums[i] >= a: piN = piN + [primeNums[i]] i += 1 f = np.array(piN) # Convert the prime list to an array. n = len(f) # Get the total number of primes found. else: f = 'ERROR: a and b in primes(a, b) must be positive integers with b > a.' n = -1 # Return an error message due to bad inputs. return f, n