Prime Testing in C: Trial Division & Eratosthenes Sieve

1. Introduction

2. What is a prime number?

2.1. Basic characteristics of prime numbers

• The smallest prime is 2 (the only even prime)
• 1 is not a prime (because it has only one divisor)
• There are infinitely many primes
• If an integer n ≥ 2 is not prime, it is always divisible by some prime ≥ 2

2.2. Concrete examples of primes

3. Basic Prime Checking Method in C (🔰 Beginner-friendly)

3.1. Trial Division (Basic)

• If N is an integer ≥ 2, check whether it is divisible by any number from 2 to N‑1
• If a divisor is found, it is a “composite number”; otherwise, it is a “prime number”

#include <stdio.h>

int is_prime(int n) {
    if (n < 2) return 0;  // Numbers ≤ 1 are not prime
    for (int i = 2; i < n; i++) {  // Check divisibility from 2 up to n-1
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num = 7;
    if (is_prime(num))
        printf("%d is a prime numbern", num);
    else
        printf("%d is not a prime numbern", num);
    return 0;
}

7 is a prime number

4. Efficient Prime Number Detection in C (Sieve of Eratosthenes & Improved Trial Division)

1. Trial Division up to √N (Optimized)
2. Sieve of Eratosthenes

4.1. Trial Division up to √N (Optimized)

#include <stdio.h>
#include <math.h>

int is_prime_optimized(int n) {
    if (n < 2) return 0;
    if (n % 2 == 0 && n != 2) return 0;  // Even numbers other than 2 are not prime
    for (int i = 3; i <= sqrt(n); i += 2) {  // Check only odd numbers (skip even)
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num = 29;
    if (is_prime_optimized(num))
        printf("%d is a prime numbern", num);
    else
        printf("%d is not a prime numbern", num);
    return 0;
}

29 is a prime number

4.2. Sieve of Eratosthenes

• Start with 2 and eliminate all its multiples
• Then eliminate multiples of the next smallest remaining number (3)
• Repeating this process leaves only prime numbers

#include <stdio.h>
#include <stdbool.h>

void sieve(int n) {
    bool prime[n + 1];
    for (int i = 0; i <= n; i++) prime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d ", p);
    printf("n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

5. Performance Comparison of Prime-Testing Algorithms in C (Speed Measurement and Optimization)

• Trial division (basic): O(N)
• Trial division up to √N (optimized): O(√N)
• Sieve of Eratosthenes (when finding primes within a range): O(N log log N)

5.1. How to Measure Execution Time

#include <stdio.h>
#include <time.h>

void measure_time(void (*func)(int), int n) {
    clock_t start, end;
    start = clock();  // measurement start

    func(n);  // execute the function being measured

    end = clock();  // measurement end
    printf("Execution time: %lf secondsn", (double)(end - start) / CLOCKS_PER_SEC);
}

5.2. Measuring Execution Time of Each Method

5.2.1. Trial Division (O(N))

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

void test_trial_division(int limit) {
    int count = 0;
    for (int i = 2; i <= limit; i++) {
        if (is_prime(i)) count++;
    }
    printf("Total primes: %dn", count);
}

5.3. Comparison of Execution Times (Graphical)

6. FAQ (Frequently Asked Questions)

Q1: Why use the square root for prime testing?

• 1 × 49
• 7 × 7 (square root)
• 49 × 1

Q2: When should the Sieve of Eratosthenes be used?

• Want to list primes from 1 to 1,000,000
• Want to efficiently test the primality of multiple numbers

Q3: Does the C environment affect the speed of prime testing?

• Type of compiler (GCC, Clang, MSVC, etc.)
• Optimization options at compile time
• CPU performance (especially affecting loop execution speed)

gcc -O3 prime.c -o prime

7. Summary and Future Learning Directions

7.1. Article Summary

🔹 What is a prime number?

• A natural number that has no divisors other than 1 and itself
• By checking up to the square root, you can reduce unnecessary calculations (time complexity O(√N))

🔹 Prime testing methods in C

🔹 Choosing the optimal algorithm

7.2. Future Learning Directions

1️⃣ More advanced prime testing algorithms

• Miller–Rabin prime test (probabilistic)
• AKS prime test (deterministic)

2️⃣ Optimization techniques in C

• Compiler optimization options (-O2, -O3)
• Parallel processing using multithreading

3️⃣ Handling large numbers in C

• Using the GMP (GNU Multiple Precision) library

7.3. Practical Project Ideas

7.4. Summary

• Trial division (basic) has a time complexity of O(N), making it slow and unsuitable for large numbers.
• √N trial division runs in O(√N), suitable for single large-number checks.
• Sieve of Eratosthenes runs in O(N log log N), allowing fast generation of prime lists.
• Choosing the optimal algorithm based on the use case is important!