java 8中的素数

Question

我试图在Java 8中编写一个简单的素数程序.下面是程序.我也希望减少代码isPrime().有一些从过滤元件2到n/2,然后再应用过滤器n%i == 0这将使isPrime无关？

import static java.util.stream.Collectors.toList;

import java.util.Arrays;
import java.util.List;
import java.util.function.Predicate;

public class Stream1 {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 20);
        // Prime number 
        System.out.println(numbers.stream()
                             .filter(Stream1::isPrime)
                             .collect(toList()));
    }

    public static boolean isPrime(int number) {
        for (int i = 2; i <= number / 2; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Answer 1

IntStream可用于生成整数流

public static boolean isPrime(int number) {
    return !IntStream.rangeClosed(2, number/2).anyMatch(i -> number%i == 0); 
}

要么

public static boolean isPrime(int number) {
    return IntStream.rangeClosed(2, number/2).noneMatch(i -> number%i == 0);
}

Answer 2

你isPrime()的效率低下。首先，您不需要除以任何大于 2 的偶数，因为初始除以 2 将捕获所有偶数非素数。其次，您将循环终止于number / 2而不是更有效的sqrt(number)。

你可以像这样重写你的方法：

public static boolean isPrime(int number) {

    // Even numbers
    if (number % 2 == 0) {
        return number == 2;
    }

    // Odd numbers
    int limit = (int)(0.1 + Math.sqrt(number));
    for (int i = 3; i <= limit; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Eratosthenes 的筛子仍然会更有效，但对于一个相对较小的问题来说，这可能是过度的。

Answer 3

您可以像这样使用埃拉托斯特尼筛法算法

public static IntStream primes(int max) {
    IntStream primes = IntStream.range(2, max);
    IntFunction<IntPredicate> sieve = n -> i -> i == n || i % n != 0;
    primes = primes.filter(sieve.apply(2));
    for (int i = 3; i * i <= max; i += 2)
        primes = primes.filter(sieve.apply(i));
    return primes;
}

和

System.out.println(primes(100).count());    // -> 25
System.out.println(primes(1000).count());   // -> 168
System.out.println(primes(10000).count());  // -> 1229