prime values

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.

[kedaman]

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

[Joacim Andersson]

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.

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!

[kedaman]

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

[kedaman]

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

[Sam Finch]

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

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

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

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

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

[kedaman]

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.

[Guv]

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.

[KWell]

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]