获取 N 的素数列表 [英] Get list of primes to N

问题描述

我正在尝试编写一个函数，它接受一个 Int 并返回直到并包括该 Int 的所有质数.

I'm trying to write a function which takes an Int and returns all of the prime numbers up to and including that Int.

例如8 的素数列表"= List(3,5,7)

for example "list of primes for 8" = List(3,5,7)

这是我目前所拥有的:

  def isPrime(i: Int): Boolean = {
    if (i <= 1)
      false
    else if (i == 2)
      true
    else
      !(2 to (i - 1)).exists(x => i % x == 0)
  }                                               //> isPrime: (i: Int)Boolean

    def getListOfPrimesToN(n : Int) = {

    }

对于函数 getListOfPrimesToN 我打算1. 创建一个大小为 n 的列表l"，并用从 0 到 n 的元素填充它.2.调用l"的map函数，对List中的每个元素调用isPrime.

for the function getListOfPrimesToN I plan to 1. create a List "l" of size n and populate it with elements ranging from 0 to n. 2. call map function of "l" and call isPrime for each element in List.

如何创建元素 1 到 N 的列表?

How to create the List of element 1 to N ?

返回所有质数的任何替代解决方案，包括 Int N 欢迎.

Any alternative solutions for returning all of the prime numbers up to and including an Int N welcome.

推荐答案

您可以使用无限流来解决此问题.如果您有一个包含所有素数的流 primes，您可以只说 primes.takeWhile(_ <= n) 来获取包含 的素数n.

You can solve this with infinite streams. If you had a stream primes of all the primes, you could just say primes.takeWhile(_ <= n) to get the primes up to and including n.

要获取所有素数，您需要从第一个素数 2 开始的所有数字流开始.然后您可以跳过所有偶数，因为它们绝对不是素数.然后你可以跳过所有其他不是质数的数字.

To get all the primes, you start with a stream of all the numbers starting from 2, the first prime. You can then skip all the even numbers since those are definitely not prime. Then you can skip all the other numbers that are not prime.

val primes = 2 #:: Stream.from(3,2).filter(isPrime)

现在您只需要 isPrime 来检查给定的数字是否为素数.如果一个数不能被任何较小的素数整除，则该数为素数.我们实际上只需要考虑平方不大于数字的素数(因为合数的最小素数因子不能大于其平方根).

Now you just need isPrime to check if a given number is prime. A number is prime if it is not divisible by any smaller prime. We actually need only consider primes whose square is not greater than the number (since, logically, a composite number's smallest prime factor can't be larger than its square root).

def isPrime(n: Int): Boolean =
  primes.takeWhile(p => p*p <= n).forall(n % _ != 0)

在 REPL 中检查:

Check this in the REPL:

scala> primes.takeWhile(_ <= 8).toList
res0: List[Int] = List(2, 3, 5, 7)

警告:这只适用于小于 Integer.MAX_VALUE 的正数.

Caveat: This only works for positive numbers smaller than Integer.MAX_VALUE.

这篇关于获取 N 的素数列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！