     Home Search   What's New Index Books Links Q & A Newsletter Banners   Feedback Tip Jar      MSDN Visual Basic Community  Title Calculate the prime factors of a product of primes plus or minus 1 in Visual Basic 2005 This example shows how to calculate the prime factors of a product of primes plus or minus 1 in Visual Basic 2005. prime, product, factor, mathematics, Visual Basic, Visual Basic 2005, VB .NET Algorithms

In around 300 BC, Euclid proved that there are an infinite number of primes using this argument:

Suppose there are a finite number of primes and they are p1, p2, ..., pn. Then none of can divide the value:

`    p1 * p2 * ... * Pn + 1`

So this new number is also prime, contradicting the assumption that p1, p2, ..., pn are all of the primes.

Recently someone suggested a similar technique for finding a big prime. The idea is to take the product of the first N primes and then add or subtract 1.

Unfortunately this method doesn't work. While the new number is not divisible by the primes you use to build the number, there may be other primes beyond those (but still smaller than the square root of the new number) that divide it.

This program demonstrates this by calculating products of the first N primes and then finding their prime factors.

The following code shows the program's Form_Load event handler. It calculates products of the first 1, 2, ..., 9 primes and calls function Factors to display their prime factors.

```Private Sub Form1_Load(ByVal sender As System.Object, ByVal _
Dim primes() As Long = {2, 3, 5, 7, 11, 13, 17, 19, 23, _
29}
Dim result As String = ""
For i As Integer = 0 To primes.Length - 1
Dim num As Long = 1
Dim txt As String = ""
For j As Integer = 0 To i
txt &= " x " & primes(j).ToString()
num *= primes(j)
Next j
txt = txt.Substring(3)
num -= 1
result &= txt & " - 1 = " & num.ToString() & " = " _
& Factors(num) & vbCrLf
num += 2
result &= txt & " + 1 = " & num.ToString() & " = " _
& Factors(num) & vbCrLf
Next i

txtResult.Text = result
txtResult.Select(0, 0)
End Sub```

The Factors function is the only part of this program that is really generally useful. It returns a string listing a number's prime factors.

The function starts by pulling factors of 2 out of the number. As long as the number is divisible by 2, the program adds a 2 to the output and divides the number by 2.

Eventually the number becomes odd (there may be remaining odd factors or, if the number is a power of two, then this step reduces the number to 1). At that point, the program starts pulling out odd factors. Starting with the test factor value 3, if the test factor value divides the number evenly, then the program adds it to the output and divides the test factor from the number. If the test factor doesn't divide the number evenly, then the program adds 2 to the test factor to consider the next odd number.

The program repeats this step until the test factor is greater than the square root of the remaining number. At that point, whatever is left of the number is prime.

```' Return the number's prime factors.
Private Function Factors(ByVal num As Long) As String
Dim result As String = ""

' Take out the 2s.
Do While num Mod 2 = 0
' This is a factor.
result &= " x 2"
num \= 2
Loop

' Take out other primes.
Dim factor As Long = 3
Do While factor * factor <= num
If num Mod factor = 0 Then
' This is a factor.
result &= " x " & factor.ToString()
num \= factor
Else
factor += 1
End If
Loop

If num > 1 Then result &= " x " & num
If result.Length = 0 Then
result = "1"
Else
result = result.Substring(3)
End If

Return result
End Function```

Incidentally, the first example that p1 * p2 * ... * pn - 1 is non prime is:

`     2 x 3 x 5 x 7 - 1 = 209 =  11 x 19`

The first example that p1 * p2 * ... * pn + 1 is non prime is:

`      2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031 =  59 x 509`

Also look here for an interesting article about the largest known prime number (as of September 28, 2008). It has around 13 million digits!  Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.  Updated 