0

I have made a code that doesn't seem to be very efficient. It only calculates a few of the primes.

This is my code:

num=float(1)
a=1

while(num>0):    # Create variable to hold the factors and add 1 and itself (all numbers have these factors)
    factors = [1, num]

    # For each possible factor
    for i in range(2, int(num/4)+3):
        # Check that it is a factor and that the factor and its corresponding factor are not already in the list
        if float(num) % i == 0 and i not in factors and float(num/i) not in factors:
            # Add i and its corresponding factor to the list
            factors.append(i)
            factors.append(float(num/i))
    num=float(num)
    number=num
# Takes an integer, returns true or false
    number = float(number)
# Check if the only factors are 1 and itself and it is greater than 1
    if (len(factors) == 2 and number > 1):
        num2=2**num-1
        factors2=[1, num]
        for i in range(2, int(num2/4)+3):
        # Check that it is a factor and that the factor and its corresponding factor are not already in the list
            if float(num2) % i == 0 and i not in factors2 and float(num2/i) not in factors2:
            # Add i and its corresponding factor to the list
                factors2.append(i)
                factors2.append(float(num2/i))
        if(len(factors2)==2 and num2>1):
            print(num2)
        a=a+1
    num=num+2

How can I make my code more efficient and be able to calculate the Mersenne Primes quicker. I would like to use the program to find any possible new perfect numbers.

Improve this question

3 Answers 3

Reset to default
1

All the solutions shown so far use bad algorithms, missing the point of Mersenne primes completely. The advantage of Mersenne primes is we can test their primality more efficiently than via brute force like other odd numbers. We only need to check an exponent for primeness and use a Lucas-Lehmer primality test to do the rest:

def lucas_lehmer(p):
    s = 4
    m = 2 ** p - 1
    for _ in range(p - 2):
        s = ((s * s) - 2) % m
    return s == 0

def is_prime(number):
    """
    the efficiency of this doesn't matter much as we're
    only using it to test the primeness of the exponents
    not the mersenne primes themselves
    """

    if number % 2 == 0:
        return number == 2

    i = 3
    while i * i <= number:
        if number % i == 0:
            return False
        i += 2

    return True

print(3)  # to simplify code, treat first mersenne prime as a special case

for i in range(3, 5000, 2):  # generate up to M20, found in 1961
    if is_prime(i) and lucas_lehmer(i):
        print(2 ** i - 1)

The OP's code bogs down after M7 524287 and @FrancescoBarban's code bogs down after M8 2147483647. The above code generates M18 in about 15 seconds! Here's up to M11, generated in about 1/4 of a second:

3
7
31
127
8191
131071
524287
2147483647
2305843009213693951
618970019642690137449562111
162259276829213363391578010288127
170141183460469231731687303715884105727
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

This program bogs down above M20, but it's not a particulary efficient implementation. It's simply not a bad algorithm.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Great idea @cdlane! May I suggest use of >> aka "Bit Shift" operator for better performance?
-1 
import math

def is_it_prime(n):

    # n is already a factor of itself 
    factors = [n]

    #look for factors
    for i in range(1, int(math.sqrt(n)) + 1):

         #if i is a factor of n, append it to the list
         if n%i == 0: factors.append(i)
         else: pass

    #if the list has more than 2 factors n is not prime
    if len(factors) > 2: return False
    #otherwise n is prime
    else: return True

n = 1
while True:

    #a prime P is a Mersenne prime if P = 2 ^ n - 1
    test = (2 ** n) - 1

    #if test is prime is also a Mersenne prime
    if is_it_prime(test):
        print(test)
    else: pass
    n += 1

Probably it will stuck to 2147483647, but you know, the next Mersenne prime is 2305843009213693951... so don't worry if it takes more time than you expected ;)

Improve this answer

1 Comment

Rather than just pasting an answer, why not explain why your answer is better or faster?
-1

If you just want to check if a number is prime, then you do not need to find all its factors. You already know 1 and num are factors. As soon as you find a third factor then the number cannot be prime. You are wasting time looking for the fourth, fifth etc. factors.

A Mersenne number is of the form 2^n - 1, and so is always odd. Hence all its factors are odd. You can halve the run-time of your loop if you only look for odd factors: start at 3 and step 2 to the next possible factor.

Factors come in pairs, one larger than the square root and one smaller. Hence you only need to look for factors up to the square root, as @Francesco's code shows. That can give you a major time saving for the larger Mersenne numbers.

Putting these two points together, your loop should be more like:

#look for factors
for i in range(3, int(math.sqrt(n)) + 1, 2):
Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.