Skip to content

Instantly share code, notes, and snippets.

@CarterA
Created January 10, 2012 06:26
Show Gist options
  • Save CarterA/1587394 to your computer and use it in GitHub Desktop.
Save CarterA/1587394 to your computer and use it in GitHub Desktop.
Primality Testing and Factorization in C
int bruteForcePrimalityTest(long int n) {
for (long int i = 2; i < n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
const int numberOfChunks = 8;
int concurrentPrimalityTestWithOnlyOddsAndSqrtLimit(long int n) {
if (n % 2 == 0) return 0;
long int max = floor(sqrt(n));
long int chunkSize = max/numberOfChunks;
__block int returnValue = 1;
dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);
dispatch_group_t group = dispatch_group_create();
for (int queueIndex = 1; queueIndex <= 2; queueIndex++) {
dispatch_group_async(group, queue, ^{
long int min = (chunkSize * (queueIndex - 1)) + 1;
long int max = chunkSize * queueIndex;
for (long int i = min; i < max; i++) {
long int possibleFactor = (2 * i) + 1;
if (n % possibleFactor == 0) {
returnValue = 0;
return;
}
}
});
}
dispatch_group_wait(group, DISPATCH_TIME_FOREVER);
dispatch_release(queue);
return returnValue;
}
int primalityTestWithOnlyOddsAndSqrtLimit(long int n) {
if (n % 2 == 0) return 0;
long int max = floor(sqrt(n));
for (long int i = 2; i < max; i++) {
if (n % ((2 * i) + 1) == 0) return 0;
}
return 1;
}
int primalityTestWithOnlyOdds(long int n) {
if (n % 2 == 0) return 0;
long int max = ((n - 1)/2);
for (long int i = 2; i < max; i++) {
if (n % ((2 * i) + 1) == 0) return 0;
}
return 1;
}
void factorize(long int n) {
if (primalityTestWithOnlyOddsAndSqrtLimit(n)) {
printf("%ld is prime.\n", n);
return;
}
long int max = floor(sqrt(n));
char *sieve = calloc(max, 1);
fillPrimeSieve(sieve, max);
factorizeWithTrialDivisionAndSieve(n, sieve);
free(sieve);
}
void fillPrimeSieve(char *sieve, long int length) {
for (long int i = 2; i <= length ; i++) {
if (!sieve[i]) {
for (long int j = 2 * i; j < length; j += i)
sieve[j] = 1;
}
}
}
void factorizeWithTrialDivisionAndSieve(long int n, char *sieve) {
long int max = floor(sqrt(n));
for (long int i = 2; i <= max; i++) {
if (sieve[i]) continue;
long int prime = i;
if (prime * prime == n) {
printf("%ld\n%ld\n", prime, prime);
break;
}
if (n % prime == 0) {
printf("%ld\n", prime);
long int otherFactor = n/prime;
if (primalityTestWithOnlyOddsAndSqrtLimit(otherFactor))
printf("%ld\n", otherFactor);
else
factorizeWithTrialDivisionAndSieve(otherFactor, sieve);
break;
}
}
}
@TopherIsSwell
Copy link

The article with explanation is here: http://cartera.me/2012/01/10/primality-testing-and-factorization-in-c/
The library is an Apple concurrency library called Grand Central Dispatch: https://developer.apple.com/documentation/dispatch

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment