Получить список простых чисел для N

Question

Я пытаюсь написать функцию, которая принимает Int и возвращает все простые числа вплоть до Int и включает Int.

"список простых чисел для 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 создать список «l» размера n и заполнить его элементами от 0 до n. 2. вызвать функцию карты «l» и вызвать isPrime для каждого элемента в списке.

Как создать список элементов с 1 по N?

Любые альтернативные решения для возврата всех простых чисел вплоть до приветствия Int N и включая Int.

Answer 1

Вы можете решить эту проблему с бесконечными потоками. Если бы у вас был поток primes всех простых чисел, вы могли бы просто сказать primes.takeWhile(_ <= n), чтобы получить простые цифры до n.

Чтобы получить все простые числа, вы начинаете с потока всех чисел, начиная с 2, первого числа. Затем вы можете пропустить все четные числа, поскольку они определенно не являются первичными. Затем вы можете пропустить все остальные номера, которые не являются первыми.

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

Теперь вам просто нужно isPrime, чтобы проверить, является ли данное число является простым. Число простое, если оно не делится на любое меньшее простое число. Нам действительно нужно рассмотреть только числа, квадрат которых не больше числа (так как логически наименьший простой коэффициент составного числа не может быть больше его квадратного корня).

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

Проверьте это в РЕПЛ:

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

Оговорка: Это работает только для положительных чисел меньше, чем Integer.MAX_VALUE.

Answer 2

Вот код соответствует:

scala> def isPrime(n: Int): Boolean = 
    | n >= 2 && (2 to math.sqrt(n).toInt).forall(n%_ != 0) 
isPrime: (n: Int)Boolean 

scala> def getListOfPrimesToN(n: Int): List[Int] = 
    | List.range(2, n+1) filter isPrime 
getListOfPrimesTON: (n: Int)List[Int] 

scala> getListOfPrimesToN(97) 
res0: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) 

Вот еще одно решение с использованием Stream:

scala> def getListOfPrimesToN(n: Int): List[Int] = { 
    | lazy val ps: Stream[Int] = 2 #:: Stream.from(3) 
       .filter(x => ps.takeWhile(p => p*p <= x).forall(x%_ != 0)) 
    | ps.takeWhile(_ <= n).toList 
    | } 
getListOfPrimesToN: (n: Int)List[Int] 

scala> getListOfPrimesToN(97) 
res0: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) 

Answer 3

Реализация алгоритма Sieve of Eratosthenes для эффективного нахождения простых чисел до заданного значения N включает в себя следующее, (фиксированный и улучшенный на this SO ответить),

implicit class Sieve(val N: Int) extends AnyVal { 
    def primesUpTo() = { 
    val isPrime = collection.mutable.BitSet(2 to N: _*) -- (4 to N by 2) 
    for (p <- 2 +: (3 to Math.sqrt(N).toInt by 2) if isPrime(p)) { 
     isPrime --= p*p to N by p 
    } 
    isPrime.toImmutable 
    } 
} 

Следовательно

10.primesUpTo.toList 
res: List(2, 3, 5, 7) 

11.primesUpTo.toList 
res: List(2, 3, 5, 7, 11) 

Примечание Find prime numbers using Scala. Help me to improve для дополнительных идей и обсуждения.

Answer 4

Как насчет этого.

def getPrimeUnder(n: Int) = { 
    require(n >= 2) 
    val ol = 3 to n by 2 toList // oddList 
    def pn(ol: List[Int], pl: List[Int]): List[Int] = ol match { 
    case Nil => pl 
    case _ if pl.exists(ol.head % _ == 0) => pn(ol.tail, pl) 
    case _ => pn(ol.tail, ol.head :: pl) 
    } 
    pn(ol, List(2)).reverse 
}