0
\$\begingroup\$

An attempt to find Mersenne primes using the Lucas-Lehmer primality test:

n=int(input("Enter n to check if 2^n-1 is a prime:"))
a=4
for i in range(0,n-2):
    b=a**2
    a=b-2
    if i==n-3:
        c=(a)%((2**n) - 1)
        if c==0:
            print((2**n) - 1 ,"is a prime number")
            break
if c!=0:
    print((2**n) - 1 ,"is not a prime number")

Can you critique this code? It is apparent that it needs improvement as it doesnt work for n<=2 and computing power increases exponentially for increasing n. I have been learning python for less than a year, I am only 15 and would love any feedback on this program.

Edit: The confusion with n-2 and n-3 is because we have to check if the (n-1)th term in the series is divisible by l = 2^n - 1 to establish that l is a Mersenne prime. But as you would have noticed the above written code considers the 0th term as 14 which is the 3rd term in the actual series. This means there is a gap of two terms between the actual series and the series procured by the program, therefore to actually study the (n-1)th term in the series , we have to consider the (n-3)th term here. Hence the mess that doesn't allow n to be <=2.

Please provide your opinion on this

\$\endgroup\$
3
  • 2
    \$\begingroup\$ The solution to the problem with n <= 2 would just be returning True for 0 < n <= 2 and False for n <= 0? \$\endgroup\$
    – Graipher
    Mar 19, 2021 at 14:34
  • 1
    \$\begingroup\$ For a general review you're in the right place. For a specific solution to the n <= 2 problem you'd unfortunately have to go to another sub-site, though I'm not convinced that it should be SO. Maybe CS. \$\endgroup\$
    – Reinderien
    Mar 19, 2021 at 14:49
  • \$\begingroup\$ Is there any way to make the code more efficient? My computer struggles for any n>25 \$\endgroup\$
    – LOHO
    Mar 19, 2021 at 15:28

1 Answer 1

1
\$\begingroup\$

The page you linked to has pseudocode, and it does s = ((s × s) − 2) mod M. And right below the pseudocode it says:

Performing the mod M at each iteration ensures that all intermediate results are at most p bits (otherwise the number of bits would double each iteration).

Do that and it'll be much faster.

And better use the same variable names as in the page you referenced, don't make up new ones, that just obfuscates the connection.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.