|
}
}</lang>
=={{header|C++}}==
{{libheader|C++ Big Integer Library}}
<lang cpp>
// Notes:
// -Algorithm is heavily based upon the example provided for C# on this page
// -The example below requires the C++ Big Integer Library be included,
// which was written by Matt McCutchen and may be found here: (https://mattmccutchen.net/bigint/)
#include "BigIntegerLibrary.hh"
#include <iostream>
//isPrime function will determine whether a given value 'n' is probably prime.
// 'k' value determines the number of times the value is tested for probable primality.
// (higher k value increases the probability that given n value is correctly identified
// as prime or not)
bool isPrime(int n, int k);
int main(int argc, const char * argv[])
{
//Checking all integers from 1 to 1000 for primality
for(int i=1; i<1000; i++)
if(isPrime(i,10))
std::cout << i << std::endl;
return 0;
}
bool isPrime(int n, int k)
{
if(n < 2)
return false;
if(n != 2 && n % 2 == 0)
return false;
if(n == 2)
return true;
int s = n - 1;
while(s % 2 == 0)
//bitwise shift right assignment
s >>= 1;
for (int i = 0; i < k; i++)
{
//'a' will be an integer in the range of 2 to n-1 inclusive
int a = rand() % (n-2) + 2;
int temp = s;
//At this step, the following calculation should be performed: mod = a^temp % n
//Because a^temp can produce rather large values unsuitable for storage as an integer,
// a datatype of BigInteger was used. The for loop is used to essentially multiply 'a'
// by itself 'temp' number of times
BigInteger mod = 1;
for(int i=0; i<temp; i++)
mod*=a;
mod %= n;
while(temp != (n - 1) && mod != 1 && mod != (n - 1))
{
mod = (mod * mod) % n;
temp = temp * 2;
}
if(mod != (n - 1) && temp % 2 == 0)
return false;
}
return true;
}
</lang>
=={{header|Common Lisp}}==
<lang lisp>(defun factor-out (number divisor)
|