Skip to content
TheChatArchiveThe Chat Archive
Human-written demonstration (OpenAssistant volunteers)· OpenAssistant (human-written)Hugging Face OpenAssistant Conversations (oasst2)

How to check quickly if a number is prime in C?

In OpenAssistant data, “assistant” turns were written by human volunteers as demonstrations. They are not model outputs.
  1. User

    How to check quickly if a number is prime in C?

  2. Assistant

    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:

    #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;
    }
    
  3. User

    What is the complexity of this algorithm?

  4. Assistant

    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)).

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.