Как работает алгоритм «Решето Эратосфена» (java)?

Question

[mk_qwerty]

Доброго времени суток, не могу понять почему в данной задаче второй цикл проходит до n/i.

Суть программы: Программа получает на вход число n как аргумент командной строки и вычисляет кол-во простых чисел, меньше или равных n.

public class primeSieve{
  public static void main(String[] args){
    int n = Integer.parseInt(args[0]);
    boolean[] isPrime = new boolean[n+1];

    for (int i = 2; i <= n; i++)
      isPrime[i]= true;

    for (int i = 2; i <= n/i; i++){
      if (isPrime[i]){
        for (int j = i; j <= n/i; j++)
          isPrime[i * j] = false;
      }
    }

    int primes = 0;
    for (int i = 2; i <= n; i++)
      if (isPrime[i]) primes++;

    System.out.println(primes);
  }
}

Answer 1

[Роман]

не могу понять почему в данной задаче второй цикл проходит до n/i.

так как нам надо найти все простые числа меньшие чем n то будет логично что все числа полученные перемножением i и j с результатом произведения больше чем n нам не нужны, таким образом, деля n на i мы находим максимально возможное j при котором результат перемножения i и j будут меньше или равен n)))

Comments

[mk_qwerty]

Понял, спасибо)