131 lines
3.3 KiB
Text
131 lines
3.3 KiB
Text
Dim Shared primes(9) As Uinteger = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
|
|
|
|
Type BigNum
|
|
Dim Data(63) As Ubyte
|
|
End Type
|
|
|
|
Function compareBigNum(a As BigNum, b As BigNum) As Integer
|
|
For i As Integer = 63 To 0 Step -1
|
|
If a.data(i) > b.data(i) Then Return 1
|
|
If a.data(i) < b.data(i) Then Return -1
|
|
Next
|
|
Exit Function
|
|
End Function
|
|
|
|
Sub multiplyBigNum(num As BigNum, factor As Uinteger)
|
|
Dim As Ulongint carry = 0
|
|
For i As Integer = 0 To 63
|
|
Dim As Ulongint product = Clngint(num.data(i)) * factor + carry
|
|
num.data(i) = product And 255
|
|
carry = product Shr 8
|
|
Next
|
|
End Sub
|
|
|
|
Function NSmooth(n As Uinteger, size As Integer) As BigNum Ptr
|
|
Dim As Uinteger i, m, indicies(Ubound(primes))
|
|
Dim As BigNum sgte(Ubound(primes))
|
|
|
|
If n < 2 Or n > 521 Then
|
|
Print "Argument 'n' out of range"
|
|
Exit Function
|
|
End If
|
|
If size < 1 Then
|
|
Print "Argument 'size' out of range"
|
|
Exit Function
|
|
End If
|
|
|
|
Dim As Boolean ok = False
|
|
For i = 0 To Ubound(primes)
|
|
If n = primes(i) Then
|
|
ok = True
|
|
Exit For
|
|
End If
|
|
Next
|
|
If Not ok Then
|
|
For i = Ubound(primes) + 1 To 521
|
|
If n = i Then
|
|
ok = True
|
|
Exit For
|
|
End If
|
|
Next
|
|
End If
|
|
If Not ok Then
|
|
Print "Must be a prime number: "; n
|
|
Exit Function
|
|
End If
|
|
|
|
Dim As BigNum Ptr ns = Callocate(size, Sizeof(BigNum))
|
|
ns[0].data(0) = 1
|
|
|
|
Dim As Uinteger sgteSize = 0
|
|
For i = 0 To Ubound(primes)
|
|
If primes(i) > n Then Exit For
|
|
sgte(sgteSize).data(0) = primes(i)
|
|
sgteSize += 1
|
|
Next
|
|
|
|
For m = 1 To size - 1
|
|
Dim As BigNum minValue = sgte(0)
|
|
For i = 0 To sgteSize - 1
|
|
If compareBigNum(sgte(i), minValue) < 0 Then minValue = sgte(i)
|
|
Next
|
|
ns[m] = minValue
|
|
For i = 0 To sgteSize - 1
|
|
If compareBigNum(ns[m], sgte(i)) = 0 Then
|
|
indicies(i) += 1
|
|
sgte(i) = ns[indicies(i)]
|
|
multiplyBigNum(sgte(i), primes(i))
|
|
End If
|
|
Next
|
|
Next
|
|
|
|
Return ns
|
|
End Function
|
|
|
|
Function BigNumToString(num As BigNum) As String
|
|
Dim As String result = ""
|
|
Dim As BigNum quotient, zeroNum, temp = num
|
|
Dim As Uinteger divisor = 10
|
|
|
|
Do
|
|
Dim As Uinteger remainder = 0
|
|
For i As Integer = 63 To 0 Step -1
|
|
Dim As Ulongint dividend = (Clngint(remainder) Shl 8) Or temp.data(i)
|
|
quotient.data(i) = dividend \ divisor
|
|
remainder = dividend Mod divisor
|
|
Next
|
|
result = Chr(remainder + 48) & result
|
|
temp = quotient
|
|
Loop While compareBigNum(temp, zeroNum) > 0
|
|
|
|
If Len(result) = 0 Then result = "0"
|
|
Return result
|
|
End Function
|
|
|
|
' Main program
|
|
Dim As Uinteger i, j, p
|
|
Dim As BigNum Ptr ns
|
|
|
|
For i = 0 To Ubound(primes)
|
|
p = primes(i)
|
|
Print !"\nThe first "; p; " -smooth numbers are:"
|
|
ns = NSmooth(p, 25)
|
|
For j = 0 To 24
|
|
Print BigNumToString(ns[j]); " ";
|
|
Next
|
|
Print
|
|
Deallocate ns
|
|
Next
|
|
|
|
For i = 1 To Ubound(primes)
|
|
p = primes(i)
|
|
Print !"\nThe 3000 to 3002 "; p; " -smooth numbers are:"
|
|
ns = NSmooth(p, 3002)
|
|
For j = 2999 To 3001
|
|
Print BigNumToString(ns[j]); " ";
|
|
Next
|
|
Print
|
|
Deallocate ns
|
|
Next
|
|
|
|
Sleep
|