P: 24

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.
 
Share this Question
Expert 5K+
P: 8,434

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 bruteforce approach, for number n just test every number from 2 to n1 to see whether it divides evenly into n. If so, n isn't prime.
  Expert 100+
P: 1,295

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 bruteforce approach, for number n just test every number from 2 to n1 to see whether it divides evenly into n. If so, n isn't prime.
bruteforce works here testing every number from 2 to the square root of n.
even then, it's brute force.
  100+
P: 114

bruteforce 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 ;)
  Expert 5K+
P: 8,434

bruteforce 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.
  100+
P: 469
 
'

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(<<<YOURVALUE>>>) = "True" Then

MsgBox("PRIME")

Else

MsgBox("NOT PRIME")

End If

  Expert 5K+
P: 8,434

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

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 :)
  100+
P: 152

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
  Expert 100+
P: 533

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 bruteforce 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
  100+
P: 152

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 bruteforce 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 bruteforce approach of course would not need to divide by each number, but by each prime found so far, up to sqr(n) as any nonprime divisor would already have been tested by its factors
Graham
 
P: 3

I know that evry prime number is of the form:
6r  1
OR
6r + 1
Except the prime numbers 3 and 5
Try it!!!!
  Expert 5K+
P: 8,434

6r  1
OR
6r + 1
What does r represent?
  Expert 100+
P: 1,295

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*r1 you wouldn't consider it. And we don't want that to happen. Even then, most of the cases it will be only redundant.
:)
 
P: 24

A little clarification on what r represents?
 
P: 1

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 selfexpanding 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
    Question stats  viewed: 7371
 replies: 15
 date asked: Oct 15 '07
