How Can I Determine if a Number is Prime in C?

Determining the Primality of a Number in C

You seek a method in C to discern whether a given integer is prime or not. For the uninitiated, a prime number is an integer greater than one that is divisible only by itself and one.

Algorithm

Before delving into C code, let's outline the algorithm for prime checking:

1. Input a number.
2. Iterate over all integers from 2 to the square root of the input number.
3. If any of these integers divides the input number without leaving a remainder, the input number is not prime.
4. If no divisors are found, the input number is prime.

C Implementation

Armed with our algorithm, let's translate it into C:

#include <stdio.h>

int isPrime(int number) {
    if (number <= 1) return 0; // 0 and 1 are not prime
    int i;
    for (i = 2; i * i <= number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("Enter an integer: ");
    scanf("%d", &num);
    printf("%d is %s\n", num, isPrime(num) ? "prime" : "not prime");
    return 0;
}

Explanation

• We check for edge cases where the number is less than or equal to 1, as they are not prime.
• Using a loop, we iterate over divisors from 2 to the square root of the input number.
• If any divisor yields a remainder of 0, the number is not prime.
• If no divisors are found, the number is declared prime.

Example Usage

Input: 13
Output: 13 is prime

Input: 9
Output: 9 is not prime

The above is the detailed content of How Can I Determine if a Number is Prime in C?. For more information, please follow other related articles on the PHP Chinese website!