CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Oct 2011
    Posts
    2

    Post Mersenne Prime Calculator! Impossibly Simple:

    So I was thinking about Mersenne primes today and started kind of obsessing with them, and decided to save myself a ton of hand work and make a simple python script that would calculate any primes in a set amount of squares of 2.

    In case you don't know what a Mersenne prime is, not too many people do, it's a prime number that is found from a square of two, 2^2=4,2^3=8,2^4=16 etc. and then subtracting one from those. For example in 2^3=8 if you subtract one from 8 you get 7, and seven is prime, it's a Mersenne prime. But with 2^4=16, 16-1=15 which is not prime, therefor not a Mersenne prime either. The trick to these is seeing how high a Mersenne prime you can get, and there are 47 as of today. Check out GIMPS and mersenne.org for more information.

    So to the code: using a basic prime finding algorithm and a bunch of for loops and an if loop I made the program. Here it is.


    for x in range(25):
    y=(2**x)-1
    prime = True
    for divisor in range(2,y):
    if y/divisor==int(y/divisor):
    prime = False
    if prime==False:
    print(y)
    else:
    print(y,"PRIME")

    As simple and sweet as anything, and by the way if you're not looking for a ton of waiting I wouldn't suggest going past maybe 30 in your range, because they start to take time. Custom ranges and such can be used. I'm thinking about only trying prime numbers because all the squares are prime and that would majorly cut down on time, but hey it's a good start. Will continue to make improvements, and I'm open to suggestions on fixings.

  2. #2
    Join Date
    Jan 2009
    Posts
    596

    Re: Mersenne Prime Calculator! Impossibly Simple:

    A standard improvement when looking for primes is to only look for factors up to the square root of the number. I've highlighted this in red (n.b. I'm assuming this function is named sqrt, as it is in C/C++):
    Code:
    for x in range(25):
        y=(2**x)-1
        prime = True
        for divisor in range(2,sqrt(y)):
            if y/divisor==int(y/divisor):
                prime = False
        if prime==False:
            print(y)
        else:
            print(y,"PRIME")
    But the people who look for Mersenne primes use very advanced techniques to do so, so you won't find any new ones this way

  3. #3
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Mersenne Prime Calculator! Impossibly Simple:

    Along the lines of what has already been discussed:
    Code:
    import math
    for x in range(2, 30):
        y = 2 ** x - 1
        prime = next(
            (False for divisor in range(2, int(math.sqrt(y))) if y % divisor == 0),
            True,
        )
        if prime:
            print(y, "PRIME")
        else:
            print(y)
    Note that the second argument to range is the number of elements, not the max.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  4. #4
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Mersenne Prime Calculator! Impossibly Simple:

    Quote Originally Posted by laserlight View Post
    Note that the second argument to range is the number of elements, not the max.
    I don't think that is correct. See the second example at http://docs.python.org/2/library/functions.html#range . Range(1,11) produces a list with ten elements: the integers between 1 and 10, inclusive.

    I think the second argument to range is the (exclusive) maximum.
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  5. #5
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Mersenne Prime Calculator! Impossibly Simple:

    Yes, my mistake.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured