Algorithm Practice: Java Stream with Example - Gap in Primes

Spend time, you won't regret.

Problem: 

The prime numbers are not regularly spaced. 

For example from 2 to 3 the gap is 1. 

From 3 to 5 the gap is 2. 

From 7 to 11 it is 4. 

Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43

A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes

We will write a function gap with parameters:

• g (integer >= 2) which indicates the gap we are looking for
• m (integer > 2) which gives the start of the search (m inclusive)
• n (integer >= m) which gives the end of the search (n inclusive)
• n won't go beyond 1100000.

In the example above gap(2, 3, 50) will return [3, 5] or (3, 5) or {3, 5} which is the first pair between 3 and 50 with a 2-gap.

So this function should return the first pair of two prime numbers spaced with a gap of g between the limits m, n if these numbers exist otherwise `nil or null or None or Nothing (or ... depending on the language).

Examples:

• gap(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7}
• gap(2, 5, 5) --> nil. In C++ {0, 0}. In F# [||]. In Kotlin, Dart and Prolog return []`
• gap(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

([193, 197] is also such a 4-gap primes between 130 and 200 but it's not the first pair)

• gap(6,100,110) --> nil or {0, 0} or ... : between 100 and 110 we have 101, 103, 107, 109 but 101-107is not a 6-gap because there is 103in between and 103-109is not a 6-gap because there is 107in between.
• You can see more examples of return in Sample Tests.

Solution:

public class GapInPrimes {

    public static void main(String[] args) {
        List<Long> result = LongStream
                .of(gap(4, 130, 200))
                .boxed()
                .collect(Collectors.toList());
        System.out.println(result);
    }

    public static long[] gap(long g, long m, long n) {
        return LongStream
                .iterate(m % 2 == 0 ? m + 1 : m, l -> l + 2)
                .limit((n - m) / 2)
                .filter(l -> BigInteger
                        .valueOf(l)
                        .isProbablePrime(5) && BigInteger
                        .valueOf(l + g)
                        .isProbablePrime(5))
                .filter(l -> {
                    return LongStream
                            .iterate(l + 2, c -> c + 2)
                            .limit((g - 2) / 2)
                            .parallel()
                            .filter(c -> BigInteger
                                    .valueOf(c)
                                    .isProbablePrime(5))
                            .mapToObj(c -> false)
                            .findAny()
                            .orElse(true);
                })
                .mapToObj(l -> new long[]{l, l + g})
                .findFirst()
                .orElse(null);
    }
}

Output:

[163, 167]

Step by step:

for gap(6.100.110)

LongStream
        .iterate(m % 2 == 0 ? m + 1 : m, l -> l + 2)
        .limit((n - m) / 2)

[101, 103, 105, 107, 109]

        .filter(l -> BigInteger
                .valueOf(l)
                .isProbablePrime(5)

[101, 103, 107, 109]

                && BigInteger
                .valueOf(l + g)
                .isProbablePrime(5)

[101, 103, 107]

.filter(l -> {
    return LongStream
            .iterate(l + 2, c -> c + 2)
            .limit((g - 2) / 2)
            .parallel()
            .filter(c -> BigInteger
                    .valueOf(c)
                    .isProbablePrime(5))
            .mapToObj(c -> false)
            .findAny()
            .orElse(true);
})

[]

for gap(4.130.200)

LongStream
        .iterate(m % 2 == 0 ? m + 1 : m, l -> l + 2)
        .limit((n - m) / 2)

[131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199]

        .filter(l -> BigInteger
                .valueOf(l)
                .isProbablePrime(5)

[131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

                && BigInteger
                .valueOf(l + g)
                .isProbablePrime(5)

[163, 193]

        .filter(l -> {
                return LongStream
                        .iterate(l + 2, c -> c + 2)
                        .limit((g - 2) / 2)
                        .parallel()
                        .filter(c -> BigInteger
                                .valueOf(c)
                                .isProbablePrime(5))
                        .mapToObj(c -> false)
                        .findAny()
                        .orElse(true);
                })

[163, 193]

                .mapToObj(l -> new long[]{l, l + g})
                .findFirst()
                .orElse(null);

[163, 167]

Maybe need time to fully understand, but it'll definitely worth for streams.

Example from Codewars

Solution by xoh