Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
 
MSDN Visual Basic Community
 
 
 
 
 
TitleCalculate the prime factors of numbers of the form 999997 in Visual Basic 6
DescriptionThis example shows how to calculate the prime factors of numbers of the form 999997 in Visual Basic 6.
Keywordsprime, product, factor, mathematics, Visual Basic, Visual Basic 6
CategoriesAlgorithms
 
Recently a bunch of fifth graders were asked to think of the largest prime numbers they could. A lot of them wrote numbers of the form 99999997. It's easy to see that these are not divisible by 2 or 5. Because the digits aren't divisible by 3, the number is also not divisible by 3 (most of them knew that trick).

In fact, the first several numbers in this format 7, 97, and 997 are prime, and it's not easy to tell whether larger numbers of this sort are prime in your head.

This program writes out several numbers in this format and displays their prime factors.

The program's Form_Load event handler loops through nine of these numbers, calling function Factors to display their prime factors.

 
Private Sub Form_Load()
Dim result As String
Dim nine As String
Dim i As Integer
Dim num As Long

    result = ""
    nine = "7"
    For i = 1 To 9
        num = CLng(nine)
        result = result & vbCrLf & Format$(num) & " = " & _
            Factors(num)
        nine = "9" & nine
    Next i

    result = Mid$(result, Len(vbCrLf) + 1)
    txtResult.Text = result
    txtResult.SelStart = 0
    txtResult.SelLength = 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
    result = ""

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

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

    If num > 1 Then result = result & " x " & Format$(num)
    If Len(result) = 0 Then
        result = "1"
    Else
        result = Mid$(result, 3)
    End If

    Factors = result
End Function
 
Incidentally, the very next number with this format (the first one that's hard to verify in your head) is non-prime:

    9997 =  13 x 769

Nice try, kids!

 
 
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated