By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,985 Members | 1,776 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,985 IT Pros & Developers. It's quick & easy.

Need a way to determine Prime Numbers

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.
Oct 15 '07 #1
Share this Question
Share on Google+
15 Replies


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 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.
Oct 15 '07 #2

kadghar
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 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.
Oct 15 '07 #3

100+
P: 114
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 ;)
Oct 15 '07 #4

Expert 5K+
P: 8,434
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.
Oct 16 '07 #5

jamesd0142
100+
P: 469
Expand|Select|Wrap|Line Numbers
  1.     '--------------
  2.     Public Function IsPrime(ByVal TestPrime As Long) As Boolean
  3.         Dim TestNum As Long
  4.         Dim TestLimit As Long
  5.  
  6.         '   Eliminate even numbers
  7.         If TestPrime Mod 2 = 0 Then Exit Function
  8.  
  9.         '   Loop through ODD numbers starting with 3
  10.         TestNum = 3
  11.         TestLimit = TestPrime
  12.         Do While TestLimit > TestNum
  13.  
  14.             If TestPrime Mod TestNum = 0 Then
  15.                 '   Uncomment this if you really want to know
  16.                 'MsgBox("Divisible by " & TestNum)
  17.                 Exit Function
  18.             End If
  19.  
  20.             '   There's logic to this.  Think about it.
  21.             TestLimit = TestPrime \ TestNum
  22.  
  23.             '   Remember, we only bother to check odd numbers
  24.             TestNum = TestNum + 2
  25.         Loop
  26.  
  27.         '   If we made it through the loop, the number is a prime.
  28.         IsPrime = True
  29.     End Function
  30.  
and usage:

Expand|Select|Wrap|Line Numbers
  1.  If IsPrime(<<<YOUR-VALUE>>>) = "True" Then
  2.             MsgBox("PRIME")
  3.         Else
  4.             MsgBox("NOT PRIME")
  5.         End If
  6.  
Oct 16 '07 #6

Expert 5K+
P: 8,434
As kadghar pointed out, TestLimit probably should be set to Sqr(TestPrime), to reduce or eliminate wasted effort.
Oct 16 '07 #7

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 :)
Oct 17 '07 #8

100+
P: 152
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
Oct 17 '07 #9

codegecko
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 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
Oct 17 '07 #10

100+
P: 152
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
Oct 17 '07 #11

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!!!!
Oct 17 '07 #12

Expert 5K+
P: 8,434
6r - 1
OR
6r + 1
What does r represent?
Oct 17 '07 #13

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

Expand|Select|Wrap|Line Numbers
  1. If n / 2 = Int(n / 2) Or n / 3 = Int(n / 3) Then
  2.     MsgBox ("This ain't a prime number buddy")
  3. End If
  4. For r = 1 To Int((n ^ 0.5) / 6) + 1
  5.     If n / (6 * r + 1) = Int(n / (6 * r + 1)) Or n / (6 * r - 1) = Int(n / (6 * r - 1)) Then
  6.         MsgBox ("This ain't a prime number buddy")
  7.     End If
  8. Next
  9.  
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.
:)
Oct 17 '07 #14

P: 24
A little clarification on what r represents?
Oct 18 '07 #15

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 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
Nov 27 '18 #16

Post your reply

Sign in to post your reply or Sign up for a free account.