Subtracting the Nearest Prime Given Two Lists using for loop and max

Question

I have two lists: (1) of primes (prime_list), and (2) of odd numbers (odd_list). I would like to find the highest prime under each odd number, but I am having some difficultly. For example, for odd number 99 I want to subtract 97.

I have been trying to use a "for loop" and max. Those concept I can grasp. I am sure there are other method, but I have only been more confused. See For Example: How to find the nearest prime number in an array, to another number in that array?

           def max_prime():
             for each_odd in odd_list:
                print(max(prime_list))

if I add (

How can I do this clean? Is it possible using max and for loop?

Answer 1

If you aren't worried about speed and just want it to be understandable you could do the following: (I changed each_odd to curr_odd to make it more readable)

closestAbove = 0 #Defining a variable for the closest larger prime
for curr_odd in odd_list: 
    for curr_prime in prime_list: #Testing each prime for each odd number
        if (closestAbove == 0) or (curr_prime > curr_odd and curr_prime < closestAbove):
            closestAbove = curr_prime
            #This test says if the number is more than the odd number
            #and less than the number we had saved before, we want it
    print(str(curr_odd) + " : " + str(closestAbove))
    closestAbove = 0 #Reset

Answer 2

You can bisect once your prime list is in sorted order, just subtract 1 from the index returned and get that prime from the list:

from bisect import bisect_left

odd_list = range(3, 50, 2)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
for each_odd in odd_list:
    ind = bisect_left(primes, each_odd)
    print(each_odd, primes[ind - 1])

Output:

(3, 2)
(5, 3)
(7, 5)
(9, 7)
(11, 7)
(13, 11)
(15, 13)
(17, 13)
(19, 17)
(21, 19)
(23, 19)
(25, 23)
(27, 23)
(29, 23)
(31, 29)
(33, 31)
(35, 31)
(37, 31)
(39, 37)
(41, 37)
(43, 41)
(45, 43)
(47, 43)
(49, 47)