-
Yo!
I'm making a program that calculates the prime values but it's getting too slow when it comes to values like a million. My method is that i divide the value with all values from 0 to that value, for instance 0 to 10, if the value is 10. But i think you don't have to divide the value with for instance 6 because you can't divide a value with something that is larger than half of the original one. I don't know how but this is something i tried to compress the time it takes to calculate the values, but it's still too slow.
-
First of all you don't need to calculate any values above the squareroot of the original value, since the the whole that is dividable with the original is one of two factor which makes the whole. For instance, 30 is:
2*15
3*10
5*6
6*5
10*3
15*2
So you see the three last pairs of factors are unnessesary, you don't need to calculate above five. sqr(30) is 5.477.. so you use int(sqr(value)) to get the upper bound.
-
Why is it the squareroot of my value?
Thanks, i'm going to test your idea
-
Kedaman got a good point there. Here's a function I quickly wrote that returns True if the value pass to the function is a prime number.
Code:
Public Function IsPrime(Number As Long) As Boolean
Dim iUbound As Long
Dim i As Long
IsPrime = True
iUbound = Int(Sqr(Number))
If iUbound >= 2 Then
For i = 2 To iUbound
If Number Mod i = 0 Then
IsPrime = False
Exit Function
End If
Next
End If
End Function
Good luck!
-
As you see, it will always be pairs of factors, and the point where the factors are in mirror is always the squareroot of the value, the second factors above are larger than the first factors. For instance 64 is:
4*16
8*8 <--
16*4
-
Thank you kedaman, i think i understand it.
Joacim, I applied iubound thing on my program and it now searches the prime values much faster!
Thanks both of you
-
BTW, i forgot one thing, if you store up each primevalue, you don't need to test each value again and again later, for instance 6, is always 3*2, so you don't need to test 6 each time. But when it comes to huge values, there are huge gaps between each prime value, so you'll save a lot of time by just testing your earlier prime values.
-
You are great! I've got my primevalue finder hundred times faster than before thanks to you!
iUbound = Sqr(number)
i = 0
l = list1.list(i)
Do while l < iUbound
k = number / l
if k = int(k) then exit for
i = i + 1
l = list1.list(i)
loop
-
I'm not quite sure what you're doing, are you trying to check if a number is prime or are you trying to get a list of its prime factors.
eg the number 246
Is Not Prime
Has Prime Factors
2*3*41
I don't know if you want to find out whether your number is prime or get a list of it's prime factors.
Either way the key to it is to find out its lowest factor
To do this we can use the theorum
Any Prime Number P>3 Satisfies the Equation P = (6N ± 1) for some integer N)
and as the lowest factor of a number is always Prime we only need to check for factors of 2,3 and numbers in the form (6N ± 1) So We Can try this code
Code:
Public Function LowestFactor(Number As Long) As Long
Dim i As Long
'Check if it's divisible by 2
If (Number Mod 2) = 0 Then
LowestFactor = 2
Exit Function
End If
'Check if it's divisible by 3
If (Number Mod 3) = 0 Then
LowestFactor = 3
Exit Function
End If
'Now check for higher numbers
For i = 7 To Fix(Sqr(Number)) Step 6 'i will always be in the form 6N + 1
'Check for a factor of i-2
If (Number Mod (i - 2)) = 0 Then
LowestFactor = i - 2
Exit Function
End If
'check for a factor of i
If (Number Mod i) = 0 Then
LowestFactor = i
Exit Function
End If
Next i
'there are no factors so the number is prime
'therefore it's lowest factor = number
LowestFactor = Number
End Function
once we have that it is very simple to check if a number is prime
Code:
Private Function IsPrime(Number As Long) As Boolean
IsPrime = (LowestFactor(Number) = Number)
End Function
we can speed this up a bit by doing a quick check to see if it satisfies one of these 4 conditions
- Number = 2
- Number = 3
- Number + 1 is divisible by 6
- Number - 1 is divisible by 6
if it does not satisfy any of these conditions it cannot be prime.
in fact there is no point checking if it = 2 or 3 because we do that anyway when finding it's lowest factor, so we just check the last one
Code:
Private Function IsPrime(Number As Long) As Boolean
If ((Number + 1) Mod 6 = 0) Or ((Number - 1) Mod 6 = 0) Then
IsPrime = (LowestFactor(Number) = Number)
Else
IsPrime = False
End If
End Function
If you want a list of its prime factors just find it's lowest factor then find the prime factors of the other factor, so all we need to do is this
Code:
Private Function PrimeFactors(Number As Long) As Collection
Dim intLowest As Integer
Dim retval As Collection
'find the lowest factor
intLowest = LowestFactor(Number)
If intLowest = Number Then
'number is prime, and has no factors other than its lowest
Set retval = New Collection
Else
'get the other factors of the number
Set retval = PrimeFactors(Number / intLowest)
End If
'add the lowest factor to the collection of factors
retval.Add intLowest
Set PrimeFactors = retval
End Function
hope it helps
-
Guv and Sam, my idea was that you make the table as you proceed searching so you'll always have all prime values lower and equal to squareroot of the number you test
also i think 6,999999999999 will only occur if you have floating points, but that's not the case now. You could of course do sqr(number+1) to be sure.
-
Thanks, Sam
Sam
I wrote a program for my HP Calculator which finds all prime factors of a number. The calculator is painfully slow. It starts by using a table containing all primes from 2 to 503, which speeds the program up a lot.
For primes beyond the table, it was dividing by all odd numbers. Your 6N+1 & 6N-1 suggestion should speed the program up a bit for numbers with large prime factors. Thanx, Sam.
Kedaman
I used 49 & 6.9999999 as an example. I would expect the square root of 49 to come out exactly 7, but would not be sure about the square root of huge numbers. Perhaps I am being too cautious, but my program adds one to the square root just to be safe. I do not see the point of generating a table of primes as you go. This just looks like extra work.
I suppose my calculator program would screw up if I enter an integer too large to be treated as an integer internally. I would expect a VB program on a PC to also screw up in this case if you do not check for it.
-
If you want a faster way to find all primes between 1 and another number (maybe the fastest: 0.29245 second for the primes between 1 and 1000000 with a PII), take a look at this post http://209.207.250.147/showthread.php?threadid=28635. See my code on page 2 http://209.207.250.147/showthread.ph...5&pagenumber=2
[Edited by kwell on 09-20-2000 at 02:02 AM]
