## Finding Adjacent Prime Numbers using Linq

October 12, 2013 Leave a comment

Suppose you have a range of numbers defined by a lower bound L and an upper bound U, the problem is to find 2 pairs of prime numbers, one of which will be the closest primes and the second pair will have the farthest distance in between. For example, given a range of integers from 1 to 20, the two most adjacent primes are 2 and 3 having a distance 1 while the least adjacent primes are 7 and 11 having a distance of 4.

Given a list of integers from 1 to 10,000 can you tell the least adjacent prime numbers? (the answer is 9551 and 9587) 🙂

Writing an algorithm that find adjacent primes can be tricky but is also short and straightforward. below is a naive vb.net implementation for this algorithm. I will not explain code in detail but basically what it does is to loop over the given range from L up to square root of U and flags all prime numbers within the range. then we compute the distance using linq and another query orders by distance in asc and desc in order to select the top 1 from each query.

Sub Main()

While TrueDim PrimeNumbers As New List(Of Integer)

Console.WriteLine(“———-Prime Distance———-“)

Console.Write(“Enter L: “)

Dim lowerLimit As String = Console.ReadLine().Trim

Console.Write(“Enter U: “)

Dim upperLimit As Integer = Console.ReadLine().Trim

Dim prime(upperLimit) As Integer

Dim c1, c2, c3 As Integer

For c1 = 2 To upperLimit

prime(c1) = 0

Next

prime(0) = 1

prime(1) = 1For c2 = 2 To Math.Sqrt(upperLimit) + 1

If prime(c2) = 0 Then

c1 = c2

c3 = 2 * c1

While c3 < upperLimit + 1

prime(c3) = 1

c3 = c3 + c1

End While

End If

Next

For c1 = 0 To upperLimit

If prime(c1) = 0 Then

PrimeNumbers.Add(c1)

End If

Next

PrimeNumbers = PrimeNumbers.Where(Function(x) x >= lowerLimit).ToList

Dim ordered = From a In PrimeNumbers Order By a Ascending Select a

Dim query = From a In ordered, b In ordered Where b > a Select P1 = a, P2 = b, Distance = Math.Abs(a – b)

query = query.GroupBy(Function(x) x.P1).Select(Function(x) x.First) ‘distinct

Dim minDistance = (From a In query Order By a.Distance Ascending Select a).Take(1).SingleOrDefault

Dim maxDistance = (From a In query Order By a.Distance Descending Select a).Take(1).SingleOrDefault

Console.WriteLine(“———————————“)

Console.WriteLine(“{0},{1} are the closest primes having distance {2}”, minDistance.P1, minDistance.P2, minDistance.Distance)

Console.WriteLine(“———————————“)

Console.WriteLine(“{0},{1} are the most distant primes having distance {2}”, maxDistance.P1, maxDistance.P2, maxDistance.Distance)

Console.WriteLine(“———————————“)

Console.ReadKey()

End While

End Sub