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

 

Advertisements

Sieve of Eratosthenes

Sieve of Eratosthenes is an ancient algorithm for finding prime numbers developed by the great mathematician Eratosthenes. Although the algorithm is centuries years old, it is still widely in use and considered one of the most common algorithms for generating prime numbers. There are couple of algorithms that outperform this one, the Sieve of Atkins and the Sieve of Subarama. I will discuss these on future posts but for the moment lets dig into Eratosthenes’s algorithm:

The algorithm takes as input an integer N, and generates all primes from 2 up to N. It works as follows:

  • generate all numbers from 2 up to N in ascending order
  • since 2 is the first prime, walk through the list of numbers and eliminate every second number from it
  • grab the next integer that survived the elimination(which is 3), and eliminate every third number from the list
  • then grab the next integer that survived that elimination(which is 5) and repeat the same process until the square of the next grabbed number is greater than N

Below is a graphical representation of the algorithm from Wikipedia:
.

It is easy to implement and test this algortihm in few lines of code. Create a console application and replace the main method with the following one and we’re done 🙂 (Special greetings to Mohammad Selek who contributed the source code).

     Sub Main()
        Dim s As String
        Console.Write("Find primes up to: ")
        s = Console.ReadLine
        Dim upperLimit As Integer = s.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
                Console.Write(c1 & "     ")
            End If
        Next
        Console.ReadKey()
    End Sub

Here is the output when N=1000