Find the nth prime between 1 and 1,000,000 in under 3 minutes - follow-up Previous question:

Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes

My mission is to find the nth prime number, based on user input 1-1,000,000. It also must be able to compute the 1,000,000th prime in under 3 minutes.
My code is relatively fast, however I need to make it calculate the 1,000,000th prime in 180 seconds or less. As of now it is taking 430 seconds, although before heavy updating last night it was taking about 20 minutes.

I am trying to accomplish this without importing any libraries (time's just for record keeping) and without making use of the sieve of Eratosthenes.  This is an assignment that I have been given, and I have been instructed to not use the help of either of those options.

import time
goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
start = time.time()
if goal &gt; 4:
    lst = [2, 3, 5, 7]
    chk = 11
    primes = 4
    while primes &lt; goal:
        j = chk**.5
        for n in lst:
            if n &gt; j:
                lst.append(chk)
                primes += 1
                break
            if chk % n == 0:
                break
        chk += 2

else:
    if goal == 1:
        print("2")
    if goal == 2:
        print("3")
    if goal == 3:
        print("5")
    if goal == 4:
        print("7")
print("Prime", str(goal), "is", str(chk - 2))
elapsed = (time.time() - start)
print(elapsed, "\n")
Trial division is entirely the wrong algorithm to use when you want to find many primes. The Sieve of Eratosthenes is much more efficient. It seems that you know that too, but have chosen a slower algorithm anyway, and now you are unhappy that it exceeds your expected running time.

Division is slower than multiplication and addition. Square root are even more work to compute. The Sieve involves neither of those expensive operations.

Nevertheless, I'll play along. If you want to do trial division, you could at least write the code better:


Eliminate special cases. You have hard-coded 2, 3, 5, 7 twice. The output format for small primes is inconsistent as well.
Eliminate redundant bookkeeping. Since primes is just the length of lst, why not use len(lst)? That frees up the variable name primes, which would be a more appropriate name for the list itself.
Name your variables better. Use candidate instead of chk. Since n is always prime, call it p instead.




import time
goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
start = time.time()

primes = [2, 3, 5, 7]
candidate = 11
while goal &gt;= len(primes):
    limit = candidate ** 0.5
    for p in primes:
        if p &gt; limit:
            primes.append(candidate)
            break
        if candidate % p == 0:
            break
    candidate += 2

print("Prime", str(goal), "is", str(primes[goal - 1]))
elapsed = (time.time() - start)
print(elapsed, "\n")


This isn't going to change the performance, but at least you would have more readable code, and less of it to manage.