Linear Sieve Algorithm
The Linear Sieve Algorithm is an efficient optimization technique used for finding prime numbers, specifically for solving the prime factorization problem. It is an improvement over the traditional Sieve of Eratosthenes, which is a popular method to generate prime numbers within a certain range. The Linear Sieve Algorithm not only generates prime numbers but also maintains a list of the smallest prime factors for all non-prime numbers in a given range. This allows for faster prime factorization of numbers, making it a valuable tool in number theory and cryptography.
The main idea behind the Linear Sieve Algorithm is to reduce the number of redundant operations by iteratively marking the smallest prime factor for each non-prime number. The algorithm starts by initializing an empty list of prime numbers and a list representing the smallest prime factors of each number in the given range. For each unmarked number in the range, the algorithm adds it to the list of prime numbers and updates the smallest prime factors for its multiples. This ensures that each composite number is processed only once, resulting in a linear time complexity of O(n). Additionally, the algorithm can quickly factorize any number within the range by dividing it by its smallest prime factor until the quotient becomes a prime number. This efficient performance makes the Linear Sieve Algorithm a powerful technique for solving problems involving prime numbers and their factors.
package Mathematics
object LinearSieve {
/**
* Method returns sequence of prime numbers which all are not greater than n
*
* @param n
* @return
*/
def getPrimeNumbers(n: Int): Seq[Int] = {
var primeNumbers = Seq.empty[Int]
val lowestPrimeDivisor: Array[Int] = Array.fill(n + 1)(0)
for (i <- 2 to n) {
if (lowestPrimeDivisor(i) == 0) {
lowestPrimeDivisor(i) = i
primeNumbers :+= i
}
var j = 0
while (j < primeNumbers.length && primeNumbers(j) <= lowestPrimeDivisor(i) && i * primeNumbers(j) <= n) {
lowestPrimeDivisor(i * primeNumbers(j)) = primeNumbers(j)
j = j + 1
}
}
primeNumbers
}
}
