Finding Adjacent Prime Numbers using Linq

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 True

Dim 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) = 1

For 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

Adjacent Primes Simulation

Adjacent Primes Simulation

 

Sequence contains no elements

Select

Image via Wikipedia

The error occurs when you try to access an object returned by a Linq query with 0 elements in the result set an
InvalidOperationException is thrown. Below is a simulation to generate the error:

Dim productQuery = From p In context.Products Where p.ID = -1 Select p

Dim p As Product = productQuery.Single()

An exception is thrown by the Single() method because the productQuery object has no products inside and the Single() method is
trying to reach the first entity in the productQuery.

To avoid this problem, we must check whether productQuery is containing some items or not. Here is the correct way to do it:

                                    Dim productQuery = From p In context.Products Where p.ID = -1 Select p 
                                    If productQuery.Count > 0 Then
                                            Dim p As Product = productQuery.Single()
                                    Else
                                            Return Nothing
                                    End If

Cross Product of arrays using LINQ

Cross Product is usually a database operation on two tables similar to a Join operation with the only difference is that the cross product will yield all the possible combinations  between the two tables. Database Management Systems such as SQL Server and Oracle provided the cross product operation easily using the cross join keyword. The problem however in real life applications appears when we want to do cross product within the application logic. Suppose you have two arrays of numbers and you want to find out all the possible combinations of the two arrays together, then pick one of those combinations that meet your specific business needs. Fortunately, with the introduction of LINQ in the past few years, cross product has become as simple as writing any other naive query. Lets take a look at the example below: consider two arrays A and B having 4 values each:

        Dim A() As Integer = {1, 2, 3, 4}
        Dim b() As Integer = {5, 6, 7, 8}

Cross product is simply obtained using the following LINQ query followed by writing out the results to console:

        Dim crossProduct = From x In A, y In b Select x, y
        For Each i In crossProduct
            Console.WriteLine(i)
        Next

This will yield the following results: