Primality Testing and Factorization in C

Brute Force Primality Test.c

int bruteForcePrimalityTest(long int n) {
	for (long int i = 2; i < n; i++) {
		if (n % i == 0) return 0;
	}
	return 1;
}

Concurrent Primality Test With Only Odds and Sqrt Limit.c

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;
}

Primality Test With Only Odds and Sqrt Limit.c

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;
}

Primality Test With Only Odds.c

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;
}

Trial Division Factorization using Prime Sieve.c

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;
		}
	}
}

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