Reputation: 4780
Does anyone happen to know of a C# Sieve of Atkin algorithm using BigInteger? From my understanding, this is the best known prime factorization algorithm currently in existence.
I currently have this function:
/// <summary>
/// Finds prime numbers using the Sieve of Atkins algorithm.
/// </summary>
/// <param name="max">The limit of the prime list.</param>
/// <returns>The list of prime numbers.</returns>
public List<int> FindPrimes(int max)
{
var isPrime = new bool[max + 1];
var sqrt = (int) Math.Sqrt(max);
Parallel.For(1, sqrt, x =>
{
var xx = x * x;
for (int y = 1; y <= sqrt; y++)
{
var yy = y * y;
var n = 4 * xx + yy;
if (n <= max && (n % 12 == 1 || n % 12 == 5))
isPrime[n] ^= true;
n = 3 * xx + yy;
if (n <= max && n % 12 == 7)
isPrime[n] ^= true;
n = 3 * xx - yy;
if (x > y && n <= max && n % 12 == 11)
isPrime[n] ^= true;
}
});
var primes = new List<int>() { 2, 3 };
for (int n = 5; n <= sqrt; n++)
{
if (isPrime[n])
{
primes.Add(n);
int nn = n * n;
for (int k = nn; k <= max; k += nn)
isPrime[k] = false;
}
}
for (int n = sqrt + 1; n <= max; n++)
if (isPrime[n])
primes.Add(n);
return primes;
}
But I would like to have a function signature that looks more like below so it can take in a single number to test and output true if the number is prime.
public bool IsPrime(BigInteger number) { ... }
Upvotes: 2
Views: 1346
Reputation: 14205
There are several related problems that you should solve in different ways:
You are asking about applying the sieve of Atkin to either test primality or factor a number into primes. This is the wrong way to go about either problem.
Upvotes: 3
Reputation: 7320
I think, by the nature of the algorithm, there's no direct way to check if N is prime.
To check if N is prime, first, you can use the easy divisors (2, 5, 7, etc), then you can generates all the Atkin primes under N, and then try to divide N by each Atkin prime. If it's divisible, then you return false. If not, then I'm afraid you will have to test all the numbers under N....
Maybe you can use some probabilistic approach, which can be far more efficient to check a single number. Try methods like Miller–Rabin or Solovay–Strassen primality test (used in RSA).
I think you will be happy : here's an implementation of Solovay, and here's an very interesting page about all the primality testing algorithms.
Upvotes: 2