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;
    }
}

- user3310115

---

尽管使用Java 8流很不错，但如果你想在Java中快速计算质数，最好还是使用传统的循环和选择一个好的算法。 - Stephen C

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);
}

- Shashwat Kumar

---

IntStream :: noneMatch 也可以使用：返回 IntStream.rangeClosed（2，number / 2）。noneMatch（i-> number％i == 0）; - srborlongan

我们能否在主流程中完成而不是在isPrime方法中完成呢？ - user3310115

@srborlongan 谢谢。已根据您的建议进行了更新。 - Shashwat Kumar

你只需要检查从2到数字的平方根。 - Stephen C

如前所述，您只需要执行“ sqrt(number)”操作即可。但更重要的是，该实现本身是错误的。问题中测试的第一个测试数字是1。这段代码将把数字1识别为质数！由于范围为空，因此不会有任何匹配。但对于数字零，它也被该代码识别为质数，并且所有负数也是如此。 - kanbagoly

Answer 2

你的 isPrime() 函数有些低效。首先，你不需要除以大于2的任何偶数，因为通过最初除以2可以捕获所有偶数非质数。其次，你终止循环时使用了 number / 2, 而不是更有效的 sqrt(number)。

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

public static boolean isPrime(int number) {

    // Low numbers
    if (number < 2) {
      return false;
    }

    // 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;
}

埃拉托斯特尼筛法可能更加有效，但对于一个相对较小的问题来说可能有些过度。

- rossum

---

OP 不是在追求优化。他只想要 Java8 的解决方案来最小化代码。此外，i*i <= number 比 i <= sqrt(number) 稍微更优一些。 - Shashwat Kumar

@ShashwatKumar OP可能不知道有更好的方法...加一。 - Eugene

@ Shaswat 对于检查小数，这可能更加优化。对于检查大数，无论是质数还是只有大的质因子，预先仅计算一次平方根更好。这取决于该方法所接收的数据。 - rossum

数字1不是质数，但是这个实现返回“true”。同样地，对于负奇数，它也会返回“true”。 - kanbagoly

感谢您的评论。代码已经修改。 - rossum

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;
}

and

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

- user4910279

Answer 4

正如 @rossum 建议的那样，您可以使用著名的埃拉托斯特尼筛法来计算质数，它可以非常快速地计算质数。

 private static BitSet primes(int limit) {
    BitSet bitSet = new BitSet(limit);
    bitSet.set(0, false);
    bitSet.set(1, false);
    bitSet.set(2, limit, true);

    for (int i = 2; i * i < limit; ++i) {

        if (bitSet.get(i)) {
            int j = i;
            int x = 2;
            while (j < limit) {
                j = i * x;
                bitSet.set(j, false);
                ++x;
            }
        }

    }

    return bitSet;
}

- Eugene

---

for (int j = i * i; j < limit; j += i) { bitSet.set(j, false); } 可能会节省很多循环。你的 x 应该从 i 开始，因为在之前的迭代中，对于从 2*i 到 i*(i-1) 的值已经被设置为 false。这样可以减少无用的计算，而乘法则被加法所取代，这通常更容易让 CPU 处理。 - Olivier Grégoire

这是一个优化版本，可减少循环使用。 - Olivier Grégoire

@OlivierGrégoire 哦，这是一个很好的观点。我会保留代码，让其他人参考你出色的评论。 - Eugene

Answer 5

您可以像下面这个测试一样使用流：

@Test
public void generatePrimeNumberListByStream(){
    List<Integer> primeNumbers =
            IntStream
                    .range(2,30)
                    .filter(number -> IntStream.range(2,number)
                            .noneMatch(divider -> number % divider == 0))
                    .boxed()
                    .collect(Collectors.toList());
    assertThat(primeNumbers, contains(2,3,5,7,11,13, 17,19, 23, 29));
}

- S. Zror

Answer 6

public static void main(String[] args) {
    List<Integer> list = IntStream.range(0, 100).filter(i -> isPrime(i)).boxed().collect(Collectors.toList());
    System.out.println(list);

}

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

- Akhil KC

Answer 7

public static boolean isPrime(int i) {
    return i % 2 != 0 && IntStream.iterate(
            3, n -> n <= (int)(Math.sqrt(i)), n -> n + 2)
            .noneMatch(k->i%k==0);
}

iterate需要3个参数，类似于for循环，第一个是起始值，第二个是停止条件，第三个是增量规则。

1和2已经是质数了，所以我们从3开始，在达到该数字的平方根之前停止。思路是假设n是正整数n=pq，其中p和q是质数。假设p大于n的平方根并且大于n的平方根。将这些不等式相乘，我们有p*q>sqrt n * sqrt n，这意味着pq>n。这与我们的假设n=pq矛盾。因此，我们可以得出结论，p小于或等于sqrt n或q小于或等于sqrt n。

n->n<=(int)(Math.sqrt(i))

最后，只要它不能被2整除，我们就不需要检查偶数，因此我们只尝试每个第二个数字。

(n->n+2)

- Spang

---

如果您解释一下提供的代码如何回答问题，那么这将是一个更好的答案。 - pppery

虽然代码可能回答了问题，但最好还是提供解释。请阅读有关当有人回答您的问题时该怎么做的说明。 - Joe Ferndz

谢谢大家，我添加了一些解释。 - Spang

Answer 8

你也可以使用谓词来实现所需的功能。

import java.util.Arrays;
import java.util.List;
import java.util.function.IntPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class PrimeUsingStream {

     public static boolean isPrime(int i) {
            IntPredicate isDivisible = index -> i % index == 0;
            return i > 1 && IntStream.range(2, i).noneMatch(isDivisible);
     }

     public static void main(String[] args) 
     {

        //System.out.println(printPrime(200));

         List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 20,23);
            // Prime number 
        System.out.println(numbers.stream()
                                 .filter(PrimeUsingStream::isPrime)
                                 .collect(Collectors.toList()));
     }

}

- Deep

Answer 9

我虽然来晚了，但我分享我的解决方案，因为有许多错误的实现被共享，而以下代码比其他 boolean isPrime(int candidate) 的解决方案性能更好。

原帖中的解决方案、被接受的答案以及许多其他答案都是不正确的，因为它们将负数、零和一视为质数，而它们并不是。请参见维基百科：https://en.wikipedia.org/wiki/Prime_number

质数（或素数）是大于1且不能被两个较小的自然数相乘得到的自然数。

该解决方案比其他 boolean isPrime(int candidate) 解决方案更快，原因如下：

• 只需要检查到 Math.sqrt(candidate) 就足够了。
• 原始帖子喜欢使用Java 8的Stream API。然而，大多数人希望素数计算更快，这比使用会带来巨大开销的Stream API更重要。
• 它利用所有素数（除2和3外）必须在6k±1处的事实。因此，它跳过可被2或3整除的数字。它仅测试（5、7）、（11、13）等组。

static boolean isPrime(int candidate) {
    if (candidate < 4) {
        return candidate > 1;
    }
    if (candidate % 2 == 0 || candidate % 3 == 0) {
        return false;
    }
    for (int i = 5; i <= Math.sqrt(candidate); i += 6) {
        if (candidate % i == 0 || candidate % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

- kanbagoly

Answer 10

Java8+ 解决方案

public static boolean isPrime(long number) {
    return number>1 && LongStream.rangeClosed(2, number / 2).noneMatch(i -> number % i == 0);
}

需要除去1！！

质数（或素数）是指一个大于1的自然数，且不能表示成两个较小自然数的乘积。

https://en.wikipedia.org/wiki/Prime_number

- alfiogang