Mersenne Prime

[gehad3003]

can any one help with Mersenne Prime numbers calculator.
A prime number is defined as being a Mersenne Prime if it is of the form 2n – 1
display all the Mersenne primes from 2 through 1,000,000. Your results should be as presented below, under testing.


2 3
3 7
5 31
7 127
13 8191
17 131071
19 524287

please provide me with some examples.

[laitinen]

I guess you mean of the form 2^n-1?

A mersenne prime number is actually all prime numbers in which all bits are set.

i.e:
11 = 3
111 = 7
11111 = 31

I guess you should create an algorithm to find prime numbers, then check if all bits are set.

Laitinen

[gehad3003]

yes you are right.
can you help me with that.
the problem is that 11 is not mersenne prime number.
any help will be appreciated.

[ovidiucucu]

Please, specify exactly what do you want!
Pseudocode, C/C++ code, whatever else?

Anyhow, you have posted in a wrong forum.
"Visual C++ Programming" forum is for "ask questions about Windows programming with Visual C++ "

So...where to move it?
In C++ (Non Visual C++ Issues) or in Algorithms & Data Structures?

[gehad3003]

i am looking for c++ code.
the course is cs 161
i am using visual studio 2005
i don't know which is the right forum to post in.

[ovidiucucu]

Here.

[ Redirected thread ]

[Zachm]

An efficient algorithm would use the Lucas Lehmer test, and should go something like this:

const int MAX_NUM = 1000000;
int number = 3;
for (int i = 2; number <= MAX_NUM; ++i)
{
	 if (IsPrime( i ))
	 {
		 if (LucasLehmerTest(i))
		 {
		  cout << number << endl;
		 }
 
	 }
	 number = (number + 1) * 2 - 1;
}

I leave you to complete the IsPrime() and LucasLehmerTest() functions yourself.
If you don't want to use the Lucas-Lehmer test, then you can just increment the "number" variable and check IsPrime(number). Note that this is a much longer check since number increases by roughly multiples of 2 while i increases by 1 on every interation.

Other optimizations can be done - for instance, you don't have to check all i's, only the odd ones (since even numbers, except for 2, are not prime).

[mmesser]

I would suggest something like this

for (int nExp = 2; nExp < 20; ++nExp)
{
    int nCandidate = 2^nExp -1;

    if (IsPrime( nCandidate ))
    {
        cout << number << endl;
    }
}

or

 
int nExp = 2;
int nCandidate;
do {
    nCandidate = 2^nExp -1;

    if (IsPrime( nCandidate ))
    {
        cout << number << endl;
    }

    ++nExp;
} while (nCandidate < 1000000);

Be careful that your ints can hold numbers as big as 100000 without overflow.


For IsPrime(), there are a number of algorithms. Lucas Lehmer is overkill. Use it if you want to search for multi-million digit primes. See www.mersenne.org.


Another algorithm is easier. nCandidate is prime if it cannot be evenly divided by any prime number up to sqrt(nCandidate).

If you already had a list of prime numbers, you could just divide by every number on your list. But you don't, so you will have to come up with a list that includes every prime, even if there are some extra numbers in it.

You could divide nCandidate by every number between 2 and sqrt(nCandidate). But that is a lot of extra dividing. You would like to avoid multiples of 2, multiples of 3, etc.

You can cut the calculation time in half by trying 2, and after that only checking odd numbers.

Since all your nCandidates are odd, you can even skip 2.

[laitinen]

for (int nExp = 2; nExp < 20; ++nExp)
{
    int nCandidate = 2^nExp -1;

    if (IsPrime( nCandidate ))
    {
        cout << number << endl;
    }
}

Be carefull with this code:

int nCandidate = 2^nExp-1;

The "^" is the bitwise or operator, not what you want...

Laitinen

[g3RC4n]

i'm working on it now, i've been intrested in prime algrathims as a way or teaching myself c++. the only thing is i don't understand what a mersenne prime is, i sorta understand

anyway, this is my code, don't work because of the int limit but fundermentally am i on the right track?

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

struct data
{
    int n;
    int prime;
    data()
    {
        prime = pow(2,n)-1;
    }
};

bool checkPrime(int num);
bool checkMesPrime(int num);
void viewVector(vector<data>buff);

const int maxNum = 5;

int main()
{
    vector<data>mesPrimes;
    data vectorBuff;
    
    for(int i = 3; i < maxNum; i+= 2)
    {
        if(checkPrime(i))
        {
            if(checkMesPrime(i))
            {
                vectorBuff.n = i;
                mesPrimes.push_back(vectorBuff);
            }
        }
    }
    viewVector(mesPrimes);
    system("pause");
    return 0;
}

bool checkPrime(int num)
{
     for(int i = 3; i*i < num +1; i+= 2)
     {
         if(num % i == 0)
         {
             return false;
         }
     }
     return true;
}

bool checkMesPrime(int num)
{
    int check = pow(2,num)-1;
    for(int i = 3; i*i < check; i+= 2)
    {
        if(check % i == 0)
        {
            return false;
        }
    }
    return true;
}

void viewVector(vector<data>buff)
{
    for(int i = 0; i < buff.size(); i++)
    {
        cout << buff[i].n << "  ";
        cout << buff[i].prime << endl;
    }     
}

[g3RC4n]

think this is it sorta, although this task is more sutited for python for the large numbers

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

//can't go any higher, numbers can't exceed 2000000000
const int maxNum = 20;
struct data
{
    int n;
    int prime;
    data(int tN)
    {
        n = tN;
        prime = pow(2,n)-1;
    }
};

bool checkPrime(int num);
bool checkMesPrime(int num);
void viewVector(vector<data>buff);

int main()
{
    vector<data>mesPrimes;
    
    for(int i = 3; i < maxNum; i+= 2)
    {
        if(checkPrime(i))
        {
            if(checkMesPrime(i))
            {
                data vecBuf(i);
                mesPrimes.push_back(vecBuf);
            }
        }
    }
    viewVector(mesPrimes);
    system("pause");
    return 0;
}

bool checkPrime(int num)
{
     for(int i = 3; i*i < num +1; i+= 2)
     {
         if(num % i == 0)
         {
             return false;
         }
     }
     return true;
}

bool checkMesPrime(int num)
{
    int check = pow(2,num)-1;
    for(int i = 3; i*i < check; i+= 2)
    {
        if(check % i == 0)
        {
            return false;
        }
    }
    return true;
}

void viewVector(vector<data>buff)
{
    for(int i = 0; i < buff.size(); i++)
    {
        cout << buff[i].n << "  ";
        cout << buff[i].prime << endl;
    }     
}

python code

import math

maxNum = 1000000

def myPow(num, nth):
    if(nth == 0):
        return 1
    number = num
    nth -= 1
    while(nth):
        number *= num
        nth -= 1
    return int(number)

class data:
    n = 0
    prime = 0
    def __init__(self,tN):
        self.n = tN
        self.prime = int(myPow(2,self.n)-1)

def checkPrime(num):
    i = 3
    while(i*i < num+1):
        if(num%i == 0):
            return 0
        i+=2
    return 1

def checkMesPrime(num):
    check = int(myPow(2,num)-1)
    i = 3
    while(i*i < num+1):
        if(num%i == 0):
            return 0
        i+=2
    return 1

def viewList(buff):
    i = 0
    while(i < len(buff)):
        print buff[i].n,"  ",buff[i].prime
        i += 1

def main():
    mesPrimes = []
    i = 3
    while(i < maxNum):
        if(checkPrime(i)):
            if(checkMesPrime(i)):
                vecBuf = data(i)
                mesPrimes.append(vecBuf)
        i += 2

    viewList(mesPrimes)

[bandwidthjunkie]

For a Mersenne Prime there is a very special linear time algorithm that determines primality called the Lucas Lehmer test (http://en.wikipedia.org/wiki/Lucas%E...senne_numbers). By primality test standards it is wildly fast. You don't need to understand it, but it works. Include the GMP number library http://gmplib.org/ to give big number support and then implement the L-L test and hey presto. But, don't expect to find any new primes, http://www.mersenne.org/ has a distributed computing project that implements an assembly optimized version of the L-L test and holds the records for many of the lagest known primes.