Primality TestDate: 11/26/2001 at 04:47:41 From: Maria Subject: Prime numbers Hi Dr Math, I want to write a program using Pascal, and I am required to enter any number in my program, which should then say if it is a prime number or not. I want to know if there is any formula for prime numbers. Date: 11/26/2001 at 08:33:19 From: Doctor Paul Subject: Re: Prime numbers This is a problem that mathematicians have been working on solving for thousands of years. There are some special types of primality tests that require some pretty advanced mathematics. But I think the most basic test is as follows: First notice that all of the divisors of a number come in pairs: For example, if I pick 48 its divisors are: 1,48 2,24 3,16 4,12 6,8 The key is to notice that all of the first numbers occur before sqrt(48). If the number had been 49, I would write the divisors as: 1,49 7,7 Here one of the divisors is sqrt(49). So what we notice is that if a number n has a divisor greater than one (which would make the number a non-prime), it must be less than or equal to sqrt(n). So you just need to run a for loop that tests to see if any number from 3 (clearly you don't need to test 2 - if the number is even and greater than two, it can't be prime) up to sqrt(n) divides evenly into the given number. If you find one, then the number isn't prime. If you don't find one, the number is prime. So how do you test divisibility? Why don't you try looking at the remainder when you divide your number n by 3, 4, 5, etc... If you ever get a remainder of zero, then you have found a factor and the number isn't prime. I don't know about pascal, but c++ has a modulus operator (the % symbol) that returns the remainder when you divide a by b. For example: 22%7 would return 1 because 22 is one more than a multiple of 7. If pascal has a similar command, this is the way to go. Otherwise, you'd have to be a bit more sly. If you are testing the number 77 for primality (it isn't prime since 77 = 7*11) and, say, you are up to 77/5 Have the computer write this as a decimal: 77/5 = 15.4 What you want to have the computer do is check to see if the number has a non-zero part after the decimal. So first run an until loop that subtracts one from the number until it is less than one and bigger than or equal to zero. In the case above, the computer would stop when the number was .4 Now test to see if this number is zero. If it is zero, then you've found a factor and the number isn't prime. Otherwise you conclude that this particular divisor didn't divide evenly into the number being tested, so you increase the divisor by one and try again. There are other - probably better - ways to test for divisibility as well. But this should at least give you a start. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 02/08/2006 at 08:34:29 From: Josh Subject: More convienent Prime Number Testing - no modulus My question isn't a question, so much as a helpful tip to you, Dr. Math. Your database of answers has helped me through the years with many of my problems, so I would like to contribute back if I can. I'm working on a prime number tester, and I was taking a look through your articles, when I noticed that one of your answers to a patron involved what to do if you had no modulus function. You told him to create a loop to subtract 1 from the division of the problem until it was less than one, then test if it was equal to 0. Instead, most of the programming languages will include some sort of flooring or rounding down function, like C++ in the math.h library. Therefore, you could make an IF statement to test "(X/Y)=FLOOR(X/Y)". For example, if you wanted to test if 10 was evenly divisble by three. 11/3 = 3.667, and FLOOR(10/3) = 3. Since the two are not equal, 3 is not a divisor of 10, and you can move on to the next number. However, testing 12 and 3, you get 12/3 = 4, and FLOOR (12/3) = 4. Since the two are equal, 4 is a divisor of 12, and you can stop. I hope this helps you, and maybe some other person out there in the world. Thanks for all your help over the years, Dr. Math. Date: 02/08/2006 at 09:51:35 From: Doctor Peterson Subject: Re: More convienent Prime Number Testing - no modulus Hi, Josh. You're right that the suggested workaround is about as inefficient as you can get; probably Dr. Paul was offering an alternative that could work in the most basic language imaginable, and didn't even want to assume it had a floor function. Actually, all you need a language to support is integer division (or, equivalently, the ability to convert a "real" or "floating point" number to an integer, which will do essentially what "floor" does). For your purposes, merely testing divisibility, your suggestion is good; one might write it as if (a/b = int(a/b)) // a is divisible by b if "int" converts a number to an integer. In fact, you can even write a "mod" function using this: mod(a, b) = a - b * int(a/b) This will be zero when a is divisible by b, and otherwise will be the remainder. All of this ignores some problems when either number is negative; I've dealt with that elsewhere, but you wouldn't need it in dealing with primes. See What is Mod? http://mathforum.org/library/drmath/sets/select/dm_mod.html If you have any further questions, feel free to write back. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ Date: 02/22/2006 at 13:31:31 From: Josh Subject: Thank you (More convienent Prime Number Testing - no modulus) Hey, I didn't even think of that! You're right about the whole negative numbers thing, and I understand the idea of working with the simplest language possible. Thanks for your comments and suggestions! - Josh |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/