Проверка простого числа

Проверка простого числа

Это одна из базовых задач алгоритмики, которая позволяет демонстрировать понимание оптимизации и математических свойств. Рассмотрим несколько подходов от простого до оптимального.

Решение 1: Базовый алгоритм — O(n) время

Проверяем все числа от 2 до n-1:

public class PrimeCheckerBasic {
    /**
     * Базовый алгоритм проверки простого числа
     * Время: O(n)
     * Пространство: O(1)
     */
    public static boolean isPrime(int n) {
        // Обработка граничных случаев
        if (n <= 1) {
            return false;  // числа <= 1 не являются простыми
        }
        if (n == 2) {
            return true;   // 2 — единственное четное простое число
        }
        if (n % 2 == 0) {
            return false;  // четные числа (кроме 2) не простые
        }
        
        // Проверяем делители от 3 до n-1
        for (int i = 3; i < n; i += 2) {  // проверяем только нечетные числа
            if (n % i == 0) {
                return false;  // нашли делитель
            }
        }
        
        return true;  // простое число
    }
    
    public static void main(String[] args) {
        System.out.println(isPrime(2));     // true
        System.out.println(isPrime(3));     // true
        System.out.println(isPrime(4));     // false
        System.out.println(isPrime(17));    // true
        System.out.println(isPrime(100));   // false
        System.out.println(isPrime(1));     // false
        System.out.println(isPrime(-5));    // false
    }
}

Решение 2: Оптимизированный алгоритм — O(√n) время

Ключевое свойство: если n имеет делитель больший чем √n, то он должен иметь и делитель меньший чем √n. Поэтому нужно проверять только до √n:

public class PrimeCheckerOptimized {
    /**
     * Оптимизированный алгоритм проверки простого числа
     * Время: O(√n)
     * Пространство: O(1)
     */
    public static boolean isPrime(int n) {
        // Граничные случаи
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        
        // Проверяем делители от 3 до sqrt(n)
        // Если число делится на число больше sqrt(n),
        // то оно должно делиться и на число меньше sqrt(n)
        int sqrt = (int) Math.sqrt(n);
        for (int i = 3; i <= sqrt; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        System.out.println(isPrime(2));     // true
        System.out.println(isPrime(3));     // true
        System.out.println(isPrime(4));     // false
        System.out.println(isPrime(17));    // true
        System.out.println(isPrime(100));   // false
        System.out.println(isPrime(97));    // true
        System.out.println(isPrime(1000000007)); // true (большое простое число)
    }
}

Решение 3: С дополнительной оптимизацией 6k±1

Все простые числа (кроме 2 и 3) имеют форму 6k±1. Это позволяет еще ускорить алгоритм:

public class PrimeCheckerAdvanced {
    /**
     * Продвинутая оптимизация: все простые числа имеют форму 6k±1
     * Время: O(√n)
     * Пространство: O(1)
     */
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;  // 2 и 3 простые
        if (n % 2 == 0 || n % 3 == 0) {
            return false;  // делится на 2 или 3
        }
        
        // Все простые числа имеют форму 6k-1 или 6k+1
        int sqrt = (int) Math.sqrt(n);
        for (int i = 5; i <= sqrt; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
}

Решение 4: С проверкой типов и обработкой особых случаев

public class PrimeCheckerRobust {
    /**
     * Надежная проверка с полной обработкой ошибок
     */
    public static boolean isPrime(long n) {
        // Отрицательные числа и числа <= 1
        if (n <= 1) {
            return false;
        }
        
        // Специальные случаи
        if (n == 2 || n == 3) {
            return true;
        }
        
        // Четные числа
        if (n % 2 == 0) {
            return false;
        }
        
        // Делится на 3
        if (n % 3 == 0) {
            return false;
        }
        
        // Проверяем делители вида 6k±1 до sqrt(n)
        long sqrt = (long) Math.sqrt(n);
        for (long i = 5; i <= sqrt; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        long[] testCases = {2, 3, 4, 5, 17, 100, -5, 0, 1, 1000000007L};
        
        for (long num : testCases) {
            System.out.printf("%d: %s%n", num, isPrime(num) ? "простое" : "не простое");
        }
    }
}

Для больших чисел: Тест Миллера-Рабина

Для очень больших чисел существуют вероятностные алгоритмы:

public class PrimeCheckerMillerRabin {
    /**
     * Тест Миллера-Рабина для больших чисел
     * Вероятностный алгоритм
     */
    public static boolean isPrime(long n, int iterations) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;
        
        // Находим r и d такие что n-1 = 2^r * d
        long d = n - 1;
        int r = 0;
        while (d % 2 == 0) {
            d /= 2;
            r++;
        }
        
        // Выполняем iterations раз
        for (int i = 0; i < iterations; i++) {
            long a = 2 + (long)(Math.random() * (n - 3));
            long x = modPow(a, d, n);
            
            if (x == 1 || x == n - 1) continue;
            
            boolean composite = true;
            for (int j = 0; j < r - 1; j++) {
                x = (x * x) % n;
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            
            if (composite) return false;
        }
        
        return true;
    }
    
    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }
}

Сравнение подходов

На собеседовании

1. Начните с базового решения, объясните идею
2. Оптимизируйте, показав, что проверка до √n достаточно
3. Обсудите граничные случаи (1, 2, отрицательные числа)
4. Упомяните более продвинутые методы для больших чисел
5. Проверьте решение на примерах