Need a way to determine Prime Numbers

[halo combat22]

I am looking for some help on a program that when you write a number it will determine it if is prime or not. Any help is appreciated.

[Killer42]

I am looking for some help on a program that when you write a number it will determine it if is prime or not. Any help is appreciated.

I'd recommend you start by looking up primes on Wikipedia. I haven't checked, but it will probably provide info on how they are determined.

Also, if you want a simple brute-force approach, for number n just test every number from 2 to n-1 to see whether it divides evenly into n. If so, n isn't prime.

[kadghar]

I'd recommend you start by looking up primes on Wikipedia. I haven't checked, but it will probably provide info on how they are determined.

Also, if you want a simple brute-force approach, for number n just test every number from 2 to n-1 to see whether it divides evenly into n. If so, n isn't prime.

brute-force works here testing every number from 2 to the square root of n.
even then, it's brute force.

[Firecore]

brute-force works here testing every number from 2 to the square root of n.
even then, it's brute force.

Everyone can use a little bit of brute force ;)

[Killer42]

brute-force works here testing every number from 2 to the square root of n.

Good point! It'd just be redundant going through the rest of them, huh.

[jamesd0142]

    '--------------
    Public Function IsPrime(ByVal TestPrime As Long) As Boolean
        Dim TestNum As Long
        Dim TestLimit As Long
 
        '   Eliminate even numbers
        If TestPrime Mod 2 = 0 Then Exit Function
 
        '   Loop through ODD numbers starting with 3
        TestNum = 3
        TestLimit = TestPrime
        Do While TestLimit > TestNum
 
            If TestPrime Mod TestNum = 0 Then
                '   Uncomment this if you really want to know
                'MsgBox("Divisible by " & TestNum)
                Exit Function
            End If
 
            '   There's logic to this.  Think about it.
            TestLimit = TestPrime \ TestNum
 
            '   Remember, we only bother to check odd numbers
            TestNum = TestNum + 2
        Loop
 
        '   If we made it through the loop, the number is a prime.
        IsPrime = True
    End Function
 

and usage:

 If IsPrime(<<<YOUR-VALUE>>>) = "True" Then
            MsgBox("PRIME")
        Else
            MsgBox("NOT PRIME")
        End If
 

[Killer42]

As kadghar pointed out, TestLimit probably should be set to Sqr(TestPrime), to reduce or eliminate wasted effort.

[halo combat22]

Private Sub Command1_Click()
Dim x, i, pr As Integer
pr = 1
x = Text1.Text
If x >= 2 Then
For i = 2 To x - 1
If x Mod i = 0 Then
pr = 0
End If
Next
If pr = 0 Then
Label1.Caption = x & " is a Composite number."
Else
Label1.Caption = x & " is a Prime number."
End If
End If
End Sub

Did it an easy way, ty but it works :)

[gpl]

I dont know how fast your processor is, but entering a number then testing for all the divisions will take a while.

Why not store a list of all the primes (up to the max number you can store in a variable) in an array or collection of some description.

Then when a number is entered, just check against the list of primes; quick and easy!

Graham

[JamieHowarth0]

I dont know how fast your processor is, but entering a number then testing for all the divisions will take a while.

Why not store a list of all the primes (up to the max number you can store in a variable) in an array or collection of some description.

Then when a number is entered, just check against the list of primes; quick and easy!

Graham

Nice idea except that there are an infinte number of prime numbers (depending on how reasonable you want to be) - checking a single value against every prime number in existence? Talk about processor strain!
I like the brute-force approach - loop up to Sqr(n) to determine whether any number divides evenly into n. If not, finish the loop, it's a prime number. If not, break the loop, it's not prime. Simple.

medicineworker

[gpl]

Nice idea except that there are an infinte number of prime numbers (depending on how reasonable you want to be) - checking a single value against every prime number in existence? Talk about processor strain!
I like the brute-force approach - loop up to Sqr(n) to determine whether any number divides evenly into n. If not, finish the loop, it's a prime number. If not, break the loop, it's not prime. Simple.

medicineworker

True, there are an infinite number ... but I was assuming that the test would be against a range limited by that which a computer could hold (bigint - 2 billion or is it 4 billion unsigned ?)

I dont know how many primaries there are in that range, but a simple binary search would make the number of comparisons a max of 32 (or is it 33).

Using larger types (floats) would encompass a much larger range, but a search would still be n (or n+1) comparisons where the range is 0 - 2^n

Of course, the figures above assumed searching for each number, the search for primaries would be far fewer


The brute-force approach of course would not need to divide by each number, but by each prime found so far, up to sqr(n) as any non-prime divisor would already have been tested by its factors
Graham

[Chirayu]

I know that evry prime number is of the form:

6r - 1

OR

6r + 1

Except the prime numbers 3 and 5

Try it!!!!

[Killer42]

6r - 1
OR
6r + 1

What does r represent?

[kadghar]

I know that evry prime number is of the form:

6r - 1

OR

6r + 1

Except the prime numbers 3 and 5

Try it!!!!

Well yes, with that you're saying that they're always near a number that is divisible by 2 and 3, which makes them not divisible by any of both.

5 is included, is the case 6*1 -1

This could help to make it faster, since you don't have to check every number from 2 to sqrt (n) ... say n is the number you want to check.

This way you'll only have to check 2, 3 and the ones with that rule.

That'll make you check the prime numbers and.. some others, but still faster.

If n / 2 = Int(n / 2) Or n / 3 = Int(n / 3) Then
    MsgBox ("This ain't a prime number buddy")
End If
For r = 1 To Int((n ^ 0.5) / 6) + 1
    If n / (6 * r + 1) = Int(n / (6 * r + 1)) Or n / (6 * r - 1) = Int(n / (6 * r - 1)) Then
        MsgBox ("This ain't a prime number buddy")
    End If
Next
 

Note I put a (+ 1) in the upper limit of the FOR, since other way when the sqrt of n is 6*r-1 you wouldn't consider it. And we don't want that to happen. Even then, most of the cases it will be only redundant.
:)

[halo combat22]

A little clarification on what r represents?

[motaxclc]

If you are using QB, you can build a quick and dirty hard divide routine.
let p=a prime candidate (odd number of course, but there are other limits you can impose if you know how prime numbers behave.)

in a loop
if p mod p' where prime' is a previously known prime number
equals 0 then p is not prime
while p' <= sqrt(p)


But this requires a lot of casheing of the known prime numbers.


I just finished developing a routine that locates prime numbers using nothing but addition - no wasted calculations. I developed a self-expanding sieve of Eratosthenes with no upper bound limit. It is not fast but is solid and steady and does not lose runtime efficiency or accuracy with higher order numbers. No repetitive division, no square checking, just shooting fish in a barrel