mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-10-28, 06:57   #1
CarmeloLabadie
 
Oct 2021

18 Posts
Default 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 <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;

Last fiddled with by retina on 2021-10-28 at 07:03 Reason: Code tags are for code
CarmeloLabadie is offline   Reply With Quote
Old 2021-10-28, 07:34   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·1,063 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2021-10-28, 07:50   #3
Brownfox
 
Brownfox's Avatar
 
Dec 2017

3×52 Posts
Default

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.
Brownfox is online now   Reply With Quote
Old 2021-10-28, 08:05   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·1,063 Posts
Default

Quote:
Originally Posted by Brownfox View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-10-28, 13:25   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·13·227 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-28, 14:58   #6
Dobri
 
"Καλός"
May 2018

73 Posts
Default

Code:
// 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;
}
Dobri is offline   Reply With Quote
Old 2021-10-28, 15:11   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

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).

Last fiddled with by paulunderwood on 2021-10-28 at 15:29
paulunderwood is offline   Reply With Quote
Old 2021-10-28, 15:17   #8
Dobri
 
"Καλός"
May 2018

73 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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 is offline   Reply With Quote
Old 2021-10-28, 23:02   #9
Dobri
 
"Καλός"
May 2018

34310 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Anyway, I'd like to see an LL test. I.e. isPrime(p,sqrt(p))&&passesLL((1<<p)-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;
}
Dobri is offline   Reply With Quote
Old 2021-10-29, 03:37   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100110101100012 Posts
Default

Quote:
Originally Posted by Dobri View Post
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)?
How about simply
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);}
Batalov is offline   Reply With Quote
Old 2021-10-29, 07:29   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·1,063 Posts
Default

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
paulunderwood is offline   Reply With Quote
Reply

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 2022-07-14 02:29
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Gaussian-Mersenne & Eisenstein-Mersenne primes siegert81 Math 2 2011-09-19 17:36
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔