-1

I'm trying to Implement types of primes in my program. In one of the type Exponent Of Mersenne, the formula to calculate is (2 power P) -1 Here P is Prime. and check the output is prime.

In calculating, I'm able to get the power but while checking for prime, the process is Hanging . and if I leave it for a very long long time then it is being calculated.

example would be, (2 power 10090) -1 and calculate if this is prime

I'm using Big Integer

I'musing this code

int prime1 = CalculatePrime(n);
BigInteger powerPrime = BigInteger.Pow(2, prime1);
bool isPrime = CheckPrime(powerPrime - 1);

private bool CheckPrime(BigInteger num)
{
    if (num == 0 || num == 1) 
        return false;

    bool isPrime = true;
    for (int j = 2; j < num; j++)
    {
        if ((num % j) == 0)
        {
            isPrime = false;
            break;
        }
    }
    return isPrime;
}

How would be this - http://www.dotnetperls.com/prime

Krishna Thota
  • 6,646
  • 14
  • 54
  • 79
  • 2
    Are you sure it's hanging and not just taking a very long time? This is a particularly poor algorithm for finding primes, so being as slow as it is it will take a *very* long time for all but the most trivial input values. – Servy Feb 27 '13 at 18:34
  • 2
    for starters, you can do `j < (num/2)` – Martin Feb 27 '13 at 18:35
  • Its taking a very long time. – Krishna Thota Feb 27 '13 at 18:36
  • 1
    The list of related questions shows quite a few questions on the topic of calculating primes. I’d suggest you to start there. – poke Feb 27 '13 at 18:37
  • Google/wikipedia are also good resources. – Servy Feb 27 '13 at 18:38
  • [This](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders) should help. It's an algorithm that should be faster than what you have, as well as text to help you understand the code. – Gyhth Feb 27 '13 at 18:38
  • You: _(2 power 10090) -1 and calculate if this is prime_ Bad example. Since `10090` is even, `2**10090 - 1` is divisible by three (`3`). – Jeppe Stig Nielsen Feb 27 '13 at 18:52
  • ok then take this 2**13466917 - 1 This is a prime. – Krishna Thota Feb 27 '13 at 18:59
  • This is not a duplicate of the noted question. That was asking about numbers in general, this is asking specifically about Mersenne numbers of the form 2**k-1. – user448810 Feb 27 '13 at 20:46
  • Instead of throwing around big numbers like 2**13466917-1, how about using 2*89-1, which is prime, as an example. It's easier than working with those big numbers, but still sufficient to address the question. – user448810 Feb 27 '13 at 20:48

3 Answers3

1

The Sieve of Eratosthenes is a particularly good algorithm for generating prime numbers that are less than a few million.

Servy
  • 202,030
  • 26
  • 332
  • 449
1

The Lucas-Lehmer test is specialized for checking whether Mersenne numbers are prime. You should use it in preference to the test you have implemented, which as you noticed can be very slow.

user448810
  • 17,381
  • 4
  • 34
  • 59
0

You can get a bit less work to do because of following:

  1. You have to check only for j < sqrt(num), not j < num
  2. You don't have to check every even number: just try with 2 at the beginning and then check only odd numbers (that's because every even number can be divided by 2, so if x cannot be divided by 2 it cannot be divided by any other even number)
MarcinJuraszek
  • 124,003
  • 15
  • 196
  • 263