Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(→{{header|PureBasic}}: Added task) |
No edit summary |
||
Line 286: | Line 286: | ||
return EXIT_SUCCESS; |
return EXIT_SUCCESS; |
||
}</lang> |
}</lang> |
||
=={{header|C sharp|C#}}== |
|||
<lang C sharp|C#> |
|||
public static class RabinMiller |
|||
{ |
|||
public static bool isPrime(int p) |
|||
{ |
|||
if(p<2) |
|||
{ |
|||
return false; |
|||
} |
|||
if(p!=2 && p%2==0) |
|||
{ |
|||
return false; |
|||
} |
|||
int s=p-1; |
|||
while(s%2==0) |
|||
{ |
|||
s>>=1; |
|||
} |
|||
for (int i = 1; i < 11;i++) |
|||
{ |
|||
Random r = new Random(); |
|||
double a = r.Next((int)p - 1) + 1; |
|||
int temp = s; |
|||
int mod = (int)Math.Pow(a, (double)temp) % p; |
|||
while(temp!=p-1 && mod!=1 && mod!=p-1) |
|||
{ |
|||
mod=(mod*mod)%p; |
|||
temp=temp*2; |
|||
} |
|||
if(mod!=p-1 && temp%2==0) |
|||
{ |
|||
return false; |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
} |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |