Простые числа на протяжении веков интересовали математиков и программистов. В этой статье мы рассмотрим различные методы определения того, является ли данное число простым или нет, с использованием языка программирования Java. Мы предоставим примеры кода для каждого метода и обсудим их плюсы и минусы. Давайте погрузимся!

Метод 1: метод грубой силы
Метод грубой силы — это самый простой метод проверки простых чисел. Он включает в себя итерацию от 2 до квадратного корня числа и проверку на делимость.

public static boolean isPrimeBruteForce(int number) {
    if (number <= 1) {
        return false;
    }
    for (int i = 2; i <= Math.sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Метод 2: пробное деление с оптимизацией
Основываясь на подходе грубой силы, мы можем оптимизировать метод пробного деления, проверяя делимость только простых чисел до квадратного корня из заданного числа.

public static boolean isPrimeTrialDivision(int number) {
    if (number <= 1) {
        return false;
    }
    if (number <= 3) {
        return true;
    }
    if (number % 2 == 0 || number % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= number; i += 6) {
        if (number % i == 0 || number % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

Метод 3: Решето Эратосфена
Решето Эратосфена — это эффективный алгоритм для генерации всех простых чисел до заданного предела. Мы можем изменить его, чтобы проверить, является ли конкретное число простым или нет.

public static boolean isPrimeSieveOfEratosthenes(int number) {
    if (number <= 1) {
        return false;
    }
    boolean[] primes = new boolean[number + 1];
    Arrays.fill(primes, true);
    primes[0] = primes[1] = false;
    for (int i = 2; i * i <= number; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= number; j += i) {
                primes[j] = false;
            }
        }
    }
    return primes[number];
}

Метод 4: Вероятностный тест на простоту — Миллера-Рабина
Тест на простоту Миллера-Рабина — это вероятностный алгоритм, который может быстро определить, является ли число простым. Хотя его точность не гарантируется во всех случаях, он широко используется благодаря своей эффективности.

import java.math.BigInteger;
import java.util.Random;
public static boolean isPrimeMillerRabin(BigInteger number, int iterations) {
    if (number.compareTo(BigInteger.ONE) <= 0) {
        return false;
    }
    if (number.compareTo(BigInteger.valueOf(3)) <= 0) {
        return true;
    }
    if (number.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        return false;
    }
    BigInteger d = number.subtract(BigInteger.ONE);
    int s = 0;
    while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        d = d.divide(BigInteger.TWO);
        s++;
    }
    for (int i = 0; i < iterations; i++) {
        BigInteger a = generateRandomBigInteger(BigInteger.TWO, number.subtract(BigInteger.ONE));
        BigInteger x = a.modPow(d, number);
        if (x.equals(BigInteger.ONE) || x.equals(number.subtract(BigInteger.ONE))) {
            continue;
        }
        boolean isProbablePrime = false;
        for (int r = 1; r < s; r++) {
            x = x.modPow(BigInteger.TWO, number);
            if (x.equals(BigInteger.ONE)) {
                return false;
            }
            if (x.equals(number.subtract(BigInteger.ONE))) {
                isProbablePrime = true;
                break;
            }
        }
        if (!isProbablePrime) {
            return false;
        }
    }
    return true;
}
private static BigInteger generateRandomBigInteger(BigInteger min, BigInteger max) {
    BigInteger range = max.subtract(min).add(BigInteger.ONE);
    Random random = new Random();
    BigInteger x = new BigInteger(range.bitLength(), random);
    while (x.compareTo(range) >= 0) {
        x = new BigInteger(range.bitLength(), random);
    }
    return x.add(min);
}

В этой статье мы рассмотрели несколько методов проверки простых чисел в Java. Мы рассмотрели метод грубой силы, пробное деление с оптимизацией, решето Эратосфена и тест на простоту Миллера-Рабина. Каждый метод имеет свои преимущества и недостатки с точки зрения временной сложности и точности. В зависимости от конкретных требований и ограничений вашего приложения вы можете выбрать наиболее подходящий метод.