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]

[code=vb]
'--------------
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("Divisi ble 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
[/code]

and usage:

[code=vb]
If IsPrime(<<<YOUR-VALUE>>>) = "True" Then
MsgBox("PRIME")
Else
MsgBox("NOT PRIME")
End If
[/code]

[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.

[CODE=vb]
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
[/CODE]

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?