Factors of a Mersenne number: Difference between revisions

Content added Content deleted

Inline

@@ Line 214: / Line 214: @@
    Return y
 }</lang>
+=={{header|BBC BASIC}}==
+<lang bbcbasic>      PRINT "A factor of M929 is "; FNmersenne_factor(929)
+      PRINT "A factor of M937 is "; FNmersenne_factor(937)
+      END
+      DEF FNmersenne_factor(P%)
+      LOCAL K%, Q%
+      IF NOT FNisprime(P%) THEN = -1
+      FOR K% = 1 TO 1000000
+        Q% = 2*K%*P% + 1
+        IF (Q% AND 7) = 1 OR (Q% AND 7) = 7 THEN
+          IF FNisprime(Q%) IF FNmodpow(2, P%, Q%) = 1 THEN = Q%
+        ENDIF
+      NEXT K%
+      DEF FNisprime(N%)
+      LOCAL D%
+      IF N% MOD 2=0 THEN = (N% = 2)
+      IF N% MOD 3=0 THEN = (N% = 3)
+      D% = 5
+      WHILE D% * D% <= N%
+        IF N% MOD D% = 0 THEN = FALSE
+        D% += 2
+        IF N% MOD D% = 0 THEN = FALSE
+        D% += 4
+      ENDWHILE
+      = TRUE
+      DEF FNmodpow(X%, N%, M%)
+      LOCAL I%, Y%, Z%
+      I% = N% : Y% = 1 : Z% = X%
+      WHILE I%
+        IF I% AND 1 THEN Y% = (Y% * Z%) MOD M%
+        Z% = (Z% * Z%) MOD M%
+        I% = I% >>> 1
+      ENDWHILE
+      = Y%
+</lang>
+Output:
+<pre>A factor of M929 is 13007
+A factor of M937 is 28111</pre>
 =={{header|C}}==
 <lang C>int isPrime(int n){
@@ Line 239: / Line 281: @@
 	} while(1);
 	printf("2^%d - 1 = 0 (mod %d)\n", q, d);}</lang>
 =={{header|C sharp}}==
 <lang csharp>using System;