Check Prime or not

Notes.md

Prime Number Testing: Methods, Complexity, and Implementations

1. Basic Concept

A prime number is a natural number greater than 1 that is only divisible by 1 and itself.

2. Efficient Prime Testing Methods

2.1 6k ± 1 Method

All primes greater than 3 are of the form 6k ± 1, where k is any integer greater than 0.

Proof:

• Every integer can be expressed as 6k + i, where i = 0, 1, 2, 3, 4, or 5.
• 6k + 0, 6k + 2, 6k + 3, and 6k + 4 are always composite.
• Only 6k + 1 and 6k + 5 (equivalent to 6k - 1) can be prime.

2.2 4n ± 1 Method

All odd numbers (including primes > 2) can be expressed as 4n ± 1.

• Less efficient than 6k ± 1, but still useful in certain contexts.
• Eliminates 50% of numbers (all even numbers) from consideration.

MISC

Any number greater than 3 that is not prime will have divisors that fall into one or more of these categories:

1. 2
2. 3
3. Prime numbers greater than 3
4. Combinations of the above

Breakdown

1. Even numbers are divisible by 2.
2. Numbers divisible by 3 have 3 as a factor.
3. If a number is not divisible by 2 or 3, its prime factors (if any) must be greater than 3.
4. Many numbers have multiple prime factors, which can be any combination of 2, 3, and larger primes.

Examples

1. 12 = 2 * 2 * 3 (combination of 2 and 3)
2. 14 = 2 * 7 (2 and a prime greater than 3)
3. 15 = 3 * 5 (3 and a prime greater than 3)
4. 30 = 2 * 3 * 5 (combination of all three categories)
5. 49 = 7 * 7 (only primes greater than 3)

3. Implementations

3.1 Recursive Approach (6k ± 1 method)

static boolean isPrime(int n, int i) {
    // Base cases
    if (n <= 3)
        return (n > 1);  // 2 and 3 are prime, 1 is not
    if (n % 2 == 0 || n % 3 == 0)
        return false;  // Numbers divisible by 2 or 3 are not prime

    // If i^2 > n, we've checked all possible factors up to √n
    if (i * i > n)
        return true;  // n is prime if we haven't found any factors yet

    // Check if n is divisible by i or i+2
    // This covers both 6k-1 and 6k+1 forms
    if (n % i == 0 || n % (i + 2) == 0)
        return false;  // n is not prime if divisible by i or i+2

    // Recursive call: move to the next pair of numbers to check
    // i+6 moves us to the next pair of 6k-1 and 6k+1
    return isPrime(n, i + 6);
}

// Usage: isPrime(n, 5)

3.2 Iterative Approach (6k ± 1 method)

static boolean isPrime(int n) {
    // Handle base cases
    if (n <= 3)
        return (n > 1);  // 2 and 3 are prime, 1 is not

    // Quick check for divisibility by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;  // Numbers divisible by 2 or 3 are not prime

    // Check all numbers of the form 6k ± 1 up to √n
    for (int i = 5; i * i <= n; i += 6) {
        // Check if n is divisible by i (6k - 1) or i + 2 (6k + 1)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;  // n is not prime if divisible by i or i+2
    }

    // If we've made it through the loop, n is prime
    return true;
}

4. Complexity Analysis

4.1 Time Complexity

• Worst-case: O(√n)
• The 6k ± 1 method reduces the number of iterations by a factor of 3 compared to checking all numbers up to √n.

4.2 Space Complexity

• Recursive: O(√n) due to the call stack.
• Iterative: O(1) as it uses only a constant amount of extra space.

5. Comparison

• The 6k ± 1 method is more efficient than the 4n ± 1 method:
  • 6k ± 1 eliminates 67% of numbers (all even numbers and multiples of 3).
  • 4n ± 1 eliminates 50% of numbers (all even numbers).
• The iterative approach is generally preferred for its constant space complexity and to avoid stack overflow for large inputs.

6. Further Optimizations

For even better performance, especially for larger numbers:

• Use the Miller-Rabin primality test for probabilistic primality testing.
• Implement the Sieve of Eratosthenes for generating all primes up to a given limit.