M
M
mk_qwerty2019-10-20 21:10:39
Java
mk_qwerty, 2019-10-20 21:10:39

How does the "Sieve of Eratosthenes" (java) algorithm work?

Good day, I can't understand why in this problem the second loop goes to n/i .
The essence of the program: The program receives the number n as an input as a command line argument and calculates the number of prime numbers less than or equal to 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 the question

In order to leave comments, you need to log in

1 answer(s)
R
Roman, 2019-10-20
@mk_qwerty

I can't understand why in this problem the second loop goes to n/i.

since we need to find all prime numbers less than n, it will be logical that we do not need all the numbers obtained by multiplying i and j with the result of a product greater than n, so dividing n by i we find the maximum possible j for which the result of multiplying i and j will be less than or equal to n)))

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question