Using the Sieve of Eratosthenes seems like a reasonable way to generate a large number of primes.
One thing that you could do is directly return your bitset representation of the primes, rather than copying it to a condensed list. This would save a bit of time in the short term, and be helpful for the next step.
for i in (list_prime(A)):
for j in (list_prime(A)[::-1]):
A few comments.
First, doing something twice is slower than doing it once! Since
list_prime(A) is repeated in both lines, it will have to re-run the Sieve of Eratosthenes: even though you know that the list of prime numbers isn't going to change, Python doesn't! Even worse, because the second line is in a loop, you're running
list_prime again for every value of
i. So you can speed it up a bit by storing that list in a variable before you get to the loops.
Second, when you have nested loops like this, you make your algorithm quadratic in the size of
list_prime(A). The issue is that you're doing the imprecise test for
j before the precise test, which is normally the slow way around. That is, you're considering all the values of
j which meet the rule "
j is a prime number" and then testing whether "
A". Instead consider all the values of
j for which "
A" first. There is exactly one of those for each
i, which is found by simple subtraction. Then check whether that
j is in your list of prime numbers. If so, you have a match. If not, you can immediately check the next
(The reason that I suggested returning the bitset representation of the list of primes is that it makes it much faster to check whether a specific number is prime.)
A few less substantial optimisations
It is good to consider the tie-breaking rules for problems like this, and listing candidates first and checking which wins afterwards is a valid way to do so.
However, it is worth thinking about the order of your algorithm before implementing the tie-breaking check. If, as is the case here, the first satisfying value is guaranteed to be the one that wins the tie break because it has the smallest
i value, you might as well just return the first one you get to.
bool_a[j] = False;
If the end result of these two lines is that
bool_a[j] must be False, just set it to false.
if statements are surprisingly slow on modern CPUs.
Whenever you find yourself appending something to a list one element at a time, consider whether you can rewrite it using list comprehensions. For example something like the following:
primes = [index for (index, is_prime) in enumerate(bool_a) if is_prime]
(However, as above, my actual recommendation is that you completely remove that step and directly return bool_a)