20211028, 06:57  #1 
Oct 2021
1_{8} Posts 
Mersenne Primes Help!!
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 LucasLehmer 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 Code:
#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 LucasLehmer 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=n1; 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; Last fiddled with by retina on 20211028 at 07:03 Reason: Code tags are for code 
20211028, 07:34  #2 
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
Firstly you need to address multipleprecision 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) LucasLehmer test, using you own addition and multiplication functions and a mod Mp function, Last fiddled with by paulunderwood on 20211028 at 07:51 
20211028, 07:50  #3 
Dec 2017
3×5^{2} Posts 
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^231) or the exponent  so you need to worry about 300,000 digit numbers?
You probably want to read up about arrays. 
20211028, 08:05  #4  
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
Quote:
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(). Last fiddled with by paulunderwood on 20211028 at 13:11 

20211028, 13:25  #5 
Feb 2017
Nowhere
2·13·227 Posts 
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. 
20211028, 14:58  #6 
"Καλός"
May 2018
7^{3} Posts 
Code:
// DevC++ 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; } 
20211028, 15:11  #7 
Sep 2002
Database er0rr
2^{2}×1,063 Posts 
This subforum 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). Last fiddled with by paulunderwood on 20211028 at 15:29 
20211028, 15:17  #8 
"Καλός"
May 2018
7^{3} Posts 

20211028, 23:02  #9  
"Καλός"
May 2018
343_{10} Posts 
Quote:
Code:
// DevC++ 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<=(p2);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; } 

20211029, 03:37  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10011010110001_{2} Posts 
That's not good, calling a double function, and casting? why (long int)? Maybe (long long int)?
How about simply Code:
Mp=(1ULL<<p)1; Hint: Code:
if(p>63) {perror("Can only handle 64bit values, hence p must be < 64\n");exit(1);} 
20211029, 07:29  #11 
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
In a general sort of way  topdown I suppose  I would do the following.
Note sqrt(n) and n2 should not be the terminating conditions for loops but assigned to variables. Last fiddled with by paulunderwood on 20211029 at 08:00 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne Primes p which are in a set of twin primes is finite?  carpetpool  Miscellaneous Math  4  20220714 02:29 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
GaussianMersenne & EisensteinMersenne primes  siegert81  Math  2  20110919 17:36 
A conjecture about Mersenne primes and nonprimes  Unregistered  Information & Answers  0  20110131 15:41 
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods  optim  PrimeNet  13  20040709 13:51 