[Java] Finding Prime Numbers Lazily using Stream

Typically, to check if a number 'n' is prime, we divide 'n' by numbers from 2 to n - 1 and check if it is divisible.

Let's apply some optimizations to this method to improve its efficiency and utilize Stream to implement lazy evaluation.

Naive Approach

The following is a naive method to check if 'n' is a prime number.

Improvements

• When expressing n = a x b, we can assume a > b without loss of generality.
  That is, we only need to check up to sqrt(n) for i. Since the sqrt() operation is expensive, we can replace it with the condition i * i <= n.
• Prime numbers greater than or equal to 5 have the form 6k ± 1. Therefore, we can reduce the number of checks by incrementing i by 6 and checking.

Improved Approach

Applying Lazy Evaluation with Stream

Java's Stream, unlike List, does not perform operations immediately when they are defined.

It waits in a state where it is defined how to calculate each element, and only performs the calculation to obtain a specific element when that element is needed.

Using this, we can create a Stream that finds prime numbers as follows.

Execution Result

Complete Code

Execution Result