424,985 Members | 1,776 Online 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
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

 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

 100+ P: 469 Expand|Select|Wrap|Line Numbers     '--------------     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: Expand|Select|Wrap|Line Numbers  If IsPrime(<<>>) = "True" Then             MsgBox("PRIME")         Else             MsgBox("NOT PRIME")         End If   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 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

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

 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 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. :) 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 