Lucas-Lehmer test: Difference between revisions

Content added Content deleted

Inline

@@ Line 150: / Line 150: @@
 int main()
 {
-	mpz_class maxcount(45);
+        mpz_class maxcount(45);
-	mpz_class found(0);
+        mpz_class found(0);
-	mpz_class check(0);
+        mpz_class check(0);
-	for( mpz_nextprime(check.get_mpz_t(), check.get_mpz_t());
+        for( mpz_nextprime(check.get_mpz_t(), check.get_mpz_t());
-	     found < maxcount;
+             found < maxcount;
-	     mpz_nextprime(check.get_mpz_t(), check.get_mpz_t()))
+             mpz_nextprime(check.get_mpz_t(), check.get_mpz_t()))
+        {
-	{
-		//std::cout << "P" << check << " " << std::flush;
+                //std::cout << "P" << check << " " << std::flush;
-		if( is_mersenne_prime(check) )
+                if( is_mersenne_prime(check) )
+                {
-		{
-			++found;
+                        ++found;
-			std::cout << "M" << check << " " << std::flush;
+                        std::cout << "M" << check << " " << std::flush;
+                }
-		}
+        }
-	}
 }
 bool is_mersenne_prime(mpz_class p)
 {
-	if( 2 == p )
+        if( 2 == p )
-		return true;
+                return true;
-	else
+        else
+        {
-	{
-		mpz_class div = pow2(p) - mpz_class(1);
+                mpz_class div = pow2(p) - mpz_class(1);
-		mpz_class s(4);
+                mpz_class s(4);
+                mpz_class s(4);
-		for( mpz_class i(3);
+                for( mpz_class i(3);
-			 i <= p;
+                         i <= p;
+                         ++i )
-			 ++i )
+                {
-		{
-			s =  (s * s - mpz_class(2)) % div ;
+                        s =  (s * s - mpz_class(2)) % div ;
+                }
-		}
-		return ( s == mpz_class(0) );
+                return ( s == mpz_class(0) );
+        }
-	}
 }
 mpz_class pow2(mpz_class exp)
 {
-	// Unfortunately, GMP doesn't have a left-shift method.
+        // Unfortunately, GMP doesn't have a left-shift method.
-	// It also doesn't have a pow() equivalent that takes arbitrary-precision exponents.
+        // It also doesn't have a pow() equivalent that takes arbitrary-precision exponents.
-	// So we have to do it the hard (and presumably slow) way.
+        // So we have to do it the hard (and presumably slow) way.
-	mpz_class ret(2);
+        mpz_class ret(2);
+        mpz_class ret(2);
-	for(mpz_class i(1); i < exp; ++i)
+        for(mpz_class i(1); i < exp; ++i)
-		ret *= mpz_class(2);
+                ret *= mpz_class(2);
+                ret *= mpz_class(2);
-	//std::cout << "pow2( " << exp << " ) = " << ret << std::endl;
+        //std::cout << "pow2( " << exp << " ) = " << ret << std::endl;
-	return ret;
+        return ret;
 }
 </pre>
@@ Line 345: / Line 345: @@
   {Application.exit 0}
 end</ocaml>
+=={{header|Pop11}}==
+Checking large numbers takes a lot of time so we limit p to
+be smaller than 1000.
+<pre>
+define Lucas_Lehmer_Test(p);
+   lvars mp = 2**p - 1, sn = 4, i;
+   for i from 2 to p - 1 do
+       (sn*sn - 2) rem mp -> sn;
+   endfor;
+   sn = 0;
+enddefine;
+lvars p = 3;
+printf('M2', '%p\n');
+while p < 1000 do
+   if Lucas_Lehmer_Test(p) then
+       printf('M', '%p');
+       printf(p, '%p\n');
+   endif;
+   p + 2 -> p;
+endwhile;
+</pre>
+The output (obtained in few seconds) is:
+<pre>
+M2
+M3
+M5
+M7
+M13
+M17
+M19
+M31
+M61
+M89
+M107
+M127
+M521
+M607
+<pre>
 =={{header|Python}}==
  from sys import stdout