Определение того, является ли число простым, — распространенная проблема в математике и информатике. В этой статье блога мы рассмотрим различные методы проверки того, является ли данное число простым, с помощью языка программирования Dart. Мы предоставим примеры кода для каждого метода, чтобы помочь вам понять и реализовать их в своих проектах.

Метод 1: Наивный подход
Наивный подход предполагает проверку того, делится ли число на любое число от 2 до квадратного корня. Если какое-либо число делит данное число нацело, оно не является простым.

bool isPrime(int number) {
  if (number < 2) return false;

  for (int i = 2; i <= Math.sqrt(number); i++) {
    if (number % i == 0) {
      return false;
    }
  }

  return true;
}

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

bool isPrime(int number) {
  if (number < 2) return false;

  for (int i = 2; i * i <= number; i++) {
    if (number % i == 0) {
      return false;
    }
  }

  return true;
}

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

bool isPrime(int number, List<int> primes) {
  if (number < 2) return false;

  for (int prime in primes) {
    if (prime * prime > number) break;
    if (number % prime == 0) return false;
  }

  return true;
}

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

bool isPrime(int number, int iterations) {
  if (number < 2) return false;

  if (number != 2 && number % 2 == 0) return false;

  int s = 0;
  int d = number - 1;
  while (d % 2 == 0) {
    d ~/= 2;
    s++;
  }

  for (int i = 0; i < iterations; i++) {
    int a = Random().nextInt(number - 3) + 2;
    int x = powMod(a, d, number);

    if (x == 1 || x == number - 1) continue;

    for (int r = 1; r < s; r++) {
      x = powMod(x, 2, number);
      if (x == 1) return false;
      if (x == number - 1) break;
    }

    if (x != number - 1) return false;
  }

  return true;
}
int powMod(int base, int exponent, int modulus) {
  int result = 1;
  while (exponent > 0) {
    if (exponent % 2 == 1) {
      result = (result * base) % modulus;
    }
    base = (base * base) % modulus;
    exponent ~/= 2;
  }
  return result;
}

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