human
How to check quickly if a number is prime in C?
gpt
If speed is a priority and your numbers are large, you're best off using a specialized library like GMP. For small numbers, a lookup table could also be viable. Otherwise, here's a reasonably efficient implementation:
```c
#include <math.h>

int is_prime(unsigned int n)
{
	unsigned int factor;
    if (n == 2) return 1; // 2 is the only even prime
	if (!(n & 1) || n == 0) return 0; // special case for even and 0

	for (factor = 3; factor <= ceil(sqrt(n)); factor += 2) // we know it's not even so we can start at 3
		if (!(n % factor)) return 0;
	return 1;
}
```
human
What is the complexity of this algorithm?
gpt
The time complexity of this algorithm is O(sqrt(n)) because the loop only runs up to the square root of the number being tested. The loop is incremented by 2, so it is testing all the odd numbers up to the square root of n. Each iteration involves a modulo operation, which is O(1) in terms of time complexity. Thus, the overall time complexity of the algorithm is O(sqrt(n)).