mersenneforum.org Mersenne Primes Help!!
 Register FAQ Search Today's Posts Mark Forums Read

 2021-10-28, 06:57 #1 CarmeloLabadie   Oct 2021 18 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 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 Code: #include #include #include 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

> reply; return 0; Last fiddled with by retina on 2021-10-28 at 07:03 Reason: Code tags are for code

 2021-10-28, 07:34 #2 paulunderwood     Sep 2002 Database er0rr 22·1,063 Posts 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, Last fiddled with by paulunderwood on 2021-10-28 at 07:51
 2021-10-28, 07:50 #3 Brownfox     Dec 2017 3×52 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^23-1) or the exponent - so you need to worry about 300,000 digit numbers? You probably want to read up about arrays.
2021-10-28, 08:05   #4
paulunderwood

Sep 2002
Database er0rr

22·1,063 Posts

Quote:
 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().

Last fiddled with by paulunderwood on 2021-10-28 at 13:11

 2021-10-28, 13:25 #5 Dr Sardonicus     Feb 2017 Nowhere 2·13·227 Posts I'm not a programmer, but it looks to me like you're looking at 2p - 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.
 2021-10-28, 14:58 #6 Dobri   "Καλός" May 2018 73 Posts Code: // Dev-C++ Code #include #include 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<
 2021-10-28, 15:11 #7 paulunderwood     Sep 2002 Database er0rr 22×1,063 Posts 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<
2021-10-28, 15:17   #8
Dobri

"Καλός"
May 2018

73 Posts

Quote:
 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.

2021-10-28, 23:02   #9
Dobri

"Καλός"
May 2018

34310 Posts

Quote:
 Originally Posted by paulunderwood Anyway, I'd like to see an LL test. I.e. isPrime(p,sqrt(p))&&passesLL((1<
Code:
// 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;
}

2021-10-29, 03:37   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100110101100012 Posts

Quote:
 Originally Posted by Dobri Code: Mp=(long int)pow(2,p)-1;
That's not good, calling a double function, and casting? why (long int)? Maybe (long long int)?
Code:
Mp=(1ULL<<p)-1;
And where are the obligatory exits for the natural limitations of this trivial method?
Hint:
Code:
if(p>63) {perror("Can only handle 64-bit  values, hence p must be < 64\n");exit(-1);}`

 2021-10-29, 07:29 #11 paulunderwood     Sep 2002 Database er0rr 22·1,063 Posts 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. Last fiddled with by paulunderwood on 2021-10-29 at 08:00

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 4 2022-07-14 02:29 emily Math 34 2017-07-16 18:44 siegert81 Math 2 2011-09-19 17:36 Unregistered Information & Answers 0 2011-01-31 15:41 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 06:32.

Mon Aug 15 06:32:07 UTC 2022 up 39 days, 1:19, 1 user, load averages: 1.27, 1.13, 1.13