Thread: Messene Primes

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221

    Messene Primes

    is this output correct?
    i am checking for messene primes.
    Code:
    #include <iostream>
    #include <iomanip>
    
    using namespace std;
    
    
    bool IsPrime (long n );
    long power2 ( long n );
    
    int  main()
    {
    
    char reply;
    
    cout << "Mersenne Primes by corey" << endl;
    cout << endl;
    cout << "n" << setw(30) << setfill(' ') << "Mersene Prime" << endl;
    cout << "==" << setw(29) << setfill(' ')<< "=============" << endl;
    
    for ( int i = 0; i < 100; i++ ) {
      if ( IsPrime ( i ) )
      power2(i);
    
    }
    
    cin >> reply;
    return 0;
      }
    
    
    bool IsPrime(long n)
      {
         int i = 0; 
    	 int counter = 0;
         	
         for ( i = 1; i <= n; i++ )
         {
            if ( n % i == 0 )
         {
     		counter++;
         }
         }
         	if (counter == 2)
    
         	return true;
    
         	else
         		
    	return false;
    
         	
         }
    
    long power2 ( long n )
    {
    
    cout << n << setw(30) << setfill(' ') << (1L << n) - 1 << endl;
    
    
    return 0;
    }
    output:
    Code:
    Mersenne Primes by corey
    
    n                 Mersene Prime
    ==                =============
    2                             3
    3                             7
    5                            31
    7                           127
    11                          2047
    13                          8191
    17                        131071
    19                        524287
    23                       8388607
    29                     536870911
    31                    2147483647
    37                            31
    41                           511
    43                          2047
    47                         32767
    53                       2097151
    59                     134217727
    61                     536870911
    67                             7
    71                           127
    73                           511
    79                         32767
    83                        524287
    89                      33554431
    97                             1
    thank you

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Of course it's not correct. 2^37 is most certainly not less than 2^31.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    thats what i thought. why does it fall apart?
    do i need to check if it's a mesenne prime ?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You can't fit 2^37 inside a long int. And I doubt you can fit 2^67 in a long long, either. You'll have to develop a way to handle longer numbers than the system provides (or work with someone else's).

  5. #5
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    Quote Originally Posted by tabstop View Post
    You can't fit 2^37 inside a long int. And I doubt you can fit 2^67 in a long long, either. You'll have to develop a way to handle longer numbers than the system provides (or work with someone else's).
    well i guess this is as far as i go, because i am not sure how to do that..
    thank you

  6. #6
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    well, this was an assignment.
    it's only CS1, but it seems like a bigger task than what we have learned...

    Assignment:

    Write a C++ program to calculate and display all the Mersenne primes from 2 through 1,000,000. Your results should be as presented below, under testing.

    Testing:

    Mersenne Primes
    n Mersenne Prime
    == ==============

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

    Press q (or any other key) followed by 'Enter' to quit:

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Well, yeah. As you can see, or if you don't trust your teacher get out your calculator and compute, 2^20 = 1048576 so n can't (shouldn't) go any higher than that.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    using this formula to make/find a mersenne prime
    (1L << n) - 1

    how is that the same as 2^n-1 ?

    dont really understand whats going on with it.
    can someone explain?
    thank you

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    How do you get from 1 to 10? From 47 to 470? From 12342 to 123420?

    Now think about how that will change when you use binary.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    thank you i got it now.
    in binary 1L shifts it to 2 and 2L would shift it to 4
    Last edited by mrsirpoopsalot; 01-31-2009 at 11:39 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help me find a better algorithm for primes
    By nick2 in forum C Programming
    Replies: 4
    Last Post: 05-30-2009, 07:59 AM
  2. Finding primes
    By scwizzo in forum C++ Programming
    Replies: 11
    Last Post: 09-10-2008, 06:15 PM
  3. primes program need some help
    By Mshock in forum C Programming
    Replies: 2
    Last Post: 04-17-2006, 07:21 PM
  4. a program that writes the primes
    By Geo-Fry in forum C++ Programming
    Replies: 8
    Last Post: 03-29-2003, 06:37 PM
  5. primes
    By godfather in forum C++ Programming
    Replies: 3
    Last Post: 05-08-2002, 01:44 PM