Mersenne Primes Help!!

[CarmeloLabadie]

My recent assignment is to find Mersenne Primes between 2 and 1,000,000. For the first part of my code, I have a function to find out if a number is prime or not. The second part of my program runs a Lucas-Lehmer test to find the Mersenne number.

My problems are many: How do I get the prime numbers in the first part of my program to loop through the second part, then display as I've formatted in my final cout statements?

This is CS1 so I'm sure the instructor is trying to weed out the less dedicated. This is my nth version, I can't do it without help anymore!

Thanks

#include <iostream>
#include <cmath>
#include <iomanip>
 
using namespace std;
 
const int LIM = 19;
long power2 (long n);
bool isPrime(int n);
 
int main()
{
     int s,n,i;
     long p; //p is an odd prime  
     int num;
     int mPrimes;
 
 
     while (num >= 1 && num <=LIM)
     {
          if (num%2!=0 && num%3 !=0 && num%5 !=0)
          {
          num = p;
          num+=2;
 
          }
     }
 
//Mersenne calculations. 
 
 s=4; //s is the Lucas-Lehmer number where  s(0)=4
 p+=2;
 n=2;
 for (i=1 ; i<p ; i++) //This for loop assigns to n the value (2^p)-1.
 {
  n=n*2;  
 }
 n=n-1;
 for (i=3 ; i<=(p) ; i++)  //Tests this many times to see if s%n==0
 {
  s=s*s;
  s-=2;
  s=s%n;
  if (s==0);
           num == mPrimes;
    } 
 
 
cout << "Mersenne Primes by Sheila Benware" << endl;
cout << setw (2) << "n" << setw (21) << "Mercenne Prime" << endl;
cout << setw (2) << "==" << setw (21) << "=============="
<< endl;
cout << setfill (' ');
cout << setw (2) << p <<setw (21) << mPrimes <<endl;
 
        char reply;
        cout << "Press q to quit: ";
        cin >> reply;
        return 0;

[paulunderwood]

Firstly you need to address multiple-precision through the use of limbs or an array of integers. Does your program deal with overflow beyond 64 bits? Are you allowed to use a library such as GMP?

If you are not allowed to use GMP then you could roll your own trial division function,and a Fermat PRP test function and run it on "p" with a few different bases to greatly weed out composite "p". Once you find a PRP "p" you can also call a trial division function to do division of Mp by 2*k*p+1 for a domain of smallish "k" and finally do a (multiprecision) Lucas-Lehmer test, using you own addition and multiplication functions and a mod Mp function,

[Brownfox]

Question: Is it the Mersenne prime that needs to be less than 1,000,000 (so you only need to consider Primes up to 2^23-1) or the exponent - so you need to worry about 300,000 digit numbers?


You probably want to read up about arrays.

[paulunderwood]

Originally Posted by Brownfox

Question: Is it the Mersenne prime that needs to be less than 1,000,000 (so you only need to consider Primes up to 2^23-1) or the exponent - so you need to worry about 300,000 digit numbers?


You probably want to read up about arrays.

Hah, good point! If the numbers are less than 1,000,000 then the problem is greatly reduced. You need to do trial division for p<=19, (maybe trail division of Mp by 2*k*p+1), and an LL test. Structure you main function with sub-functions TF and LL. Call the latter if the former passes.

Looking at you code, you assign num with p -- this looks wrong.

Does C++ do exponentiation? At least you could shift 1 left by p and subtract 1.

Hint: for the "TF" function you might want to use sqrt().

[Dr Sardonicus]

I'm not a programmer, but it looks to me like you're looking at 2^p - 1 for odd primes p < 20.

I note that there is one even prime number. It may yield a Mersenne prime.

I don't know whether the assignment requires you to use LL, but (as already noted) for such small exponents, trial division is pretty quick.

Trial division would also avoid a possible difficulty: You might want to consider whether the computation s = s*s could cause an integer overflow.

[Dobri]

// Dev-C++ Code
#include <iostream>
#include <math.h>

using namespace std;

bool PrimeCheck(long int n)
{
    long int i,imax;
    if (n<=1) return false;if (n==2) return true;if (n%2==0) return false;
    imax=(long int)floor(sqrt(n));for(i=3;i<=imax;i+=2){if(n%i==0){return false;}}
    return true;
}

int main()
{
    long int i,MRange,MpRange;
    MpRange=1000000;MRange=(long int)ceil(log2(MpRange+1));
    for(i=2;i<=MRange;i++){if(PrimeCheck(i)==true){if(PrimeCheck(((long int)pow(2,i)-1))==true){cout<<i<<"\n";}}}
    return 0;
}

[paulunderwood]

This sub-forum is for help not complete solutions!

Anyway, I'd like to see an LL test. I.e. isPrime(p,sqrt(p))&&passesLL((1<<p)-1).

[Dobri]

Originally Posted by paulunderwood

This sub-forum is for help not complete solutions!

I did not provide a complete solution. The OP still has to compute the Mp from the output I provided.
Also, the OP still has to display the result according to the format in their final cout statements.

[Dobri]

Originally Posted by paulunderwood

Anyway, I'd like to see an LL test. I.e. isPrime(p,sqrt(p))&&passesLL((1<<p)-1).

// Dev-C++ Code
#include <iostream>
#include <math.h>

using namespace std;

bool PrimeCheck(long long int n)
{
    long long int i,imax;
    if(n<=1){return false;}if(n==2){return true;}if(n%2==0){return false;}
    imax=(long int)floor(sqrt(n));for(i=3;i<=imax;i+=2){if(n%i==0){return false;}}
    return true;
}

bool LL(long long int p)
{
    long long int i,Mp,s;
    if(p<=1){return false;}if(p==2){return true;}if(p%2==0){return false;}
    s=4;Mp=(long int)pow(2,p)-1;for(i=1;i<=(p-2);i++){s=((s*s)-2)%Mp;}
    if(s==0){return true;}else{return false;}
}

int main()
{
    long long int i,MRange,MpRange;
    MpRange=1000000;MRange=(long int)ceil(log2(MpRange+1));
    for(i=2;i<=MRange;i++){if(PrimeCheck(i)==true){if(LL(i)==true){cout<<i<<"\n";}}}
    return 0;
}

[Batalov]

Originally Posted by Dobri

Mp=(long int)pow(2,p)-1;

That's not good, calling a double function, and casting? why (long int)? Maybe (long long int)?
How about simply

Mp=(1ULL<<p)-1;

And where are the obligatory exits for the natural limitations of this trivial method?
Hint:

if(p>63) {perror("Can only handle 64-bit  values, hence p must be < 64\n");exit(-1);}

[paulunderwood]

In a general sort of way -- top-down I suppose -- I would do the following.

• If withinLimits(n,1000000) && isMersennePrime(n) then printLine(n).
  
• isMersennePrime(n) iff n==2 || (isPrime(n) && passesLL(n))
  
• isPrime(n) iff n%i != 0 for i = 2 up to sqrt(n)
  
• passesLL(n) iff s(n-2)==0 where s(0)=4 and s(k)=(s(k-1)*(k-1)-2)%Mn

Note sqrt(n) and n-2 should not be the terminating conditions for loops but assigned to variables.