-
Paul282 : add STEP 2 at each For .. Next when you check for prime. You save time.
[Digital-X-Treme] : I post the code monday because i've not it at home. But i can explain my method.
Make a array(1-IndexLastNumberChecked). Where IndexLastNumberChecked = Int(LastNumberChecked/2)
All the Array is initialize to 0 (by defaut in VB)
At the end, the array contain 0 if the corresponding number is prime and 1 if it is not. The corresponding number is find like this. Index i in the array correspond to the number i*2+1. Then Array(1) => 3, Array(2) => 5, Array(3) => 7...
Principle
At all index i in the array, you remove (then you put 1 at place of 0) to all multiple of the current number you check.
A visual exemple
At the beginnig.
Array(1)=0
Array(2)=0
Array(3)=0
Array(4)=0
Array(5)=0
Array(6)=0
Array(7)=0
Array(8)=0
Array(9)=0
Array(10)=0
...
Array(IndexLastNumberChecked)=0
Step 1 : Remove all multiple of the array(1) (number 3)
Array(1)=0
Array(2)=0
Array(3)=0
Array(4)=1 ' this one
Array(5)=0
Array(6)=0
Array(7)=1 ' this one
Array(8)=0
Array(9)=0
Array(10)=1 ' this one
...
Array(IndexLastNumberChecked)=? depend of the index number
Step 2 : Remove all multiple of the array(2) (number 5)
Array(1)=0
Array(2)=0
Array(3)=0
Array(4)=1
Array(5)=0
Array(6)=0
Array(7)=1 ' this one
Array(8)=0
Array(9)=0
Array(10)=1
...
Array(IndexLastNumberChecked)=? depend of the index number
Step 3 : Remove all multiple of the array(3) (number 7)
Array(1)=0
Array(2)=0
Array(3)=0
Array(4)=1
Array(5)=0
Array(6)=0
Array(7)=1
Array(8)=0
Array(9)=0
Array(10)=1 ' this one
...
Array(IndexLastNumberChecked)=? depend of the index number
Step 4 : Remove all multiple of the array(5) (number 11)
(the Array(4) isn't a prime because the value is equal to 1)
Array(1)=0
Array(2)=0
Array(3)=0
Array(4)=1
Array(5)=0
Array(6)=0
Array(7)=1
Array(8)=0
Array(9)=0
Array(10)=1
...
Array(IndexLastNumberChecked)=? depend of the index number
Step ... until you reach Array(LastNumberToCheck)
where LastNumberToCheck = (((2*IndexLastNumberChecked)/2)-1)/2
because for all one greater, you doesn't find a multiple in the array.
I know it's a quite confuse (and my english isn't good), but tomorrow it will be more clear with the code.
-
Here is the code of my method
Create a form with this controls :
A command button name CmdFindPrime1
A command button name CmdFindPrime2
A text box named TxtNbrMax
A text box named TxtUpdtTab
A text box named TxtNo
A text box named TxtNumber
A text box named TxtTime
A label box named LblNbrMax
A label box named LblUpdtTab
A label box named LblNo
A label box named LblNumber
Add in the form code
Code:
Option Explicit
Private Declare Function QueryPerformanceCounter Lib "kernel32" (lpPerformanceCount As Currency) As Long
Private Declare Function QueryPerformanceFrequency Lib "kernel32" (lpFrequency As Currency) As Long
Dim Prime() As Long
Dim MaxPrime As Long
Dim NumPrime As Long
Dim NbrPrime As Long
Dim IdxNbrMax As Long
Dim NbrMax As Long
Dim IncrementeTab As Long
Dim i As Long
Dim Start As Currency, Finish As Currency, Freq As Currency
Private Sub CmdFindPrime1_Click()
QueryPerformanceCounter Start
Method1
QueryPerformanceCounter Finish
QueryPerformanceFrequency Freq
TxtTime = (CDbl(Finish - Start) * CDbl(Freq) / 10 / 1000) & " secondes"
'Debug.Print (CDbl(Finish - Start) * CDbl(Freq) / 10) & " secondes"
End Sub
Private Sub CmdFindPrime2_Click()
QueryPerformanceCounter Start
Methode2
QueryPerformanceCounter Finish
QueryPerformanceFrequency Freq
TxtTime = (CDbl(Finish - Start) * CDbl(Freq) / 10 / 1000) & " second(s)"
End Sub
Sub Method1()
IncrementeTab = Me.TxtUpdtTab
ReDim Prime(IncrementeTab)
MaxPrime = IncrementeTab
NumPrime = 0
NbrMax = Me.TxtNbrMax
Prime(NumPrime) = 2
Dim Nbr As Long
For Nbr = 3 To NbrMax Step 2
If IsPrime(Nbr) Then
If NumPrime = MaxPrime Then
MaxPrime = MaxPrime + IncrementeTab
ReDim Preserve Prime(MaxPrime)
End If
NumPrime = NumPrime + 1
Prime(NumPrime) = Nbr
'Me.TxtNo = NbrPrime
'Me.TxtNumber = Nbr
'DoEvents
End If
Next Nbr
Me.TxtNo = NumPrime + 1 ' +1 because we start the array at 0
Me.TxtNumber = Prime(NumPrime)
End Sub
Function IsPrime(Nbr As Long) As Boolean
'Dim i As Long
Dim LastNumToCheck As Long
LastNumToCheck = Int(Sqr(Nbr)) + 1
i = 1
While i <= NumPrime
If Nbr Mod Prime(i) = 0 Then
GoTo IsPrime_Err
End If
If Prime(i) > LastNumToCheck Then
GoTo IsPrime_End
End If
i = i + 1
Wend
IsPrime_End:
IsPrime = True
Exit Function
IsPrime_Err:
IsPrime = False
End Function
Function Methode2()
Dim i As Long
Dim j As Long
Dim jStart As Long
Dim jAdd As Long
NumPrime = 0
Dim IdxNbrMaxTest As Long
' Max index in the table
IdxNbrMax = Int((Me.TxtNbrMax - 1) / 2)
' index of the last number to check (remove multiple)
' because for the other, there is no multiple in the table
IdxNbrMaxTest = Int(((Me.TxtNbrMax) / 2 - 1) / 2)
' Redim Prime with all the number
ReDim Prime(IdxNbrMax)
For i = 1 To IdxNbrMaxTest
' Whe check all the elems of the table. We bring only those equal to 0
' Because those elems are prime
If Prime(i) = 0 Then
' Number i*2+1 is prime
NumPrime = NumPrime + 1
NbrPrime = i * 2 + 1
jAdd = NbrPrime
jStart = i + jAdd
' Remove from the table all multiple (value => 1)
For j = jStart To IdxNbrMax Step jAdd
Prime(j) = 1
Next j
End If
Next i
For i = IdxNbrMaxTest + 1 To IdxNbrMax
If Prime(i) = 0 Then
' Number i*2+1 is prime
NumPrime = NumPrime + 1
NbrPrime = i * 2 + 1
End If
Next
Me.TxtNo = NumPrime + 1 ' +1 because 2 is prime and it is not in the array
Me.TxtNumber = NbrPrime
End Function
Private Sub Form_Load()
TxtNbrMax = 100000
TxtUpdtTab = 100
TxtNo = ""
TxtNumber = ""
TxtTime = ""
LblNbrMax.Caption = "Last cheked number"
LblNo.Caption = "N° Prime"
LblNumber.Caption = "Last Prime Number"
LblUpdtTab.Caption = "Increment array by (only for method 1)"
CmdFindPrime1.Caption = "Find all pimes : Method 1"
CmdFindPrime2.Caption = "Find all pimes : Method 2"
End Sub
-
let me have a play with it
-
Question! I think you may have a bug in method2, I think you took a short cut which is "i*2+1 is prime"
This is not true, This was once thought to be true but there are exceptions to this rule (not many as I recal though)
Does this mean you get disqualified ???? :D
-
The 'i*2+1 is prime' is always true if Prime(i)=0
A short demonstration
Bring J a number between 1 and the last index of Prime()
You say that if Prime(j)=0, 2*j+1 isn't always a prime number
Then if Prime(J)=0 and if the refer number isn't a prime number, there is at least one prime divisor K different from 2*j+1.
Bring l=(K-1)/2
Then Prime(l) refer to a prime number
and l is < j
But when i passed to the index J or the array, I put 1 to all multiple of K, then Prime(j) must be equal to 1
Then it don't be equal to 0
Then for all index J, if prime(j)=0 => 2*j+1 is prime
You can also, print all the number i found and you will see that all one is prime.
Then i'm not disqualified.
-
*Dr Evil voice*
Riiiiight.
;)
-
This is the inline asm way to do sqrt (as fast as i can think of.) It's prolly the same routine that c uses, but without all the error checking...
long int temp
...
temp = NumberToSqrt
asm {
fild dword ptr [temp] ;integer load
fsqrt
fistp dword ptr [temp] ;integer store and pop
}
my "top score" for all ints (2 to 65535) is about 0.05 sec using a different method to KWell (because I am limited by memory.) The memory you need for the huge array seems to be the only limitation to KWell's method.
-
With the 'normal' method (using division), my 'top score' is 0.0909 second and with the other (using area) 0.02005 second for all primes between 2 and 66535.
Jimbob42, witch language did you use ? ASM, C or VB ? And with witch method ?
