1,13,17,221 are the factors of 221. (there may be more, but don’t think so)
I would’ve initially thought 221 would be a prime number, but I ended finding out that it has two other factors, 13 and 17. So, how can you figure out if a number a prime or composite number?
One simple algorithm is to find the square root of the number and then consider all the primes less than or equal to that square root. Now divide the original number by each of those primes, continuing until you have either found a division with a remainder of 0 or until you’ve exhausted your list of prime factors. If you never get a 0 remainder, the number is prime. In your example, the square root is between 14 and 15, so you must try trial division by (at most) 2,3,5,7,11,and 13. The last such division proves that 221 is composite, as you already know. There are much more efficient algorithms for larger primes, but the mathematical machinery for implementing them is considerably more complex.
-
Archives
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
-
Meta
If it is not an obvious prime number..try division by 11, 13, 17, 19.
References :
Elbow grease, he-he, that is, you have to test ‘em just like Ms Dee suggested. Check against all the primes less that sqrt(221). Gets really hard to do when the numbers get to be thousands of digits long, but by jings, that’s what cryptography counts on!
References :
Because its a number that have 2 or more numbers other than itself or 1 like a prime number
References :
There is a way by Eratosthenes, in which you write numbers from one to whichever number you are looking for, and then go about as follows:
Cross out 1, since 1 isn’t prime. Here you have 2, the first prime number; circle it but cross out all of its multiples. Find the next number that hasn’t been crossed out, which will be 3, and circle it. Cross out all of the multiples of 3. Keep going like this until the number you’ve found is either crossed out or circled.
Another way that is a lot easier is prime factorization. You factor a number into its prime factors.
Since there are numbers that look like primes or that are very large, there are some helpful rules of thumb to figure out a number’s factors by just looking at it.
Divisibility by 2: A number ending in an even number or 0 if greater than 2 is divisible by 2.
A number whose digits add up to a number divisible by 3 is divisible by 3.
I won’t list them all, but there is an excellent website on finding a number’s divisibility:
http://www.mathleague.com/help/wholenumbers/wholenumbers.htm#divisibilitytests
Another way that is rather foolproof is to divide the number by the first prime number other than 2 (considering 221 isn’t even); we know that it won’t be divisible by 3 (example above), 5 (doesn’t end in 5 or 0), 7 (we see right away that 21 divides evenly into 7 but the remainder 200 won’t), etc. So we just keep going until we find a prime that divides it. If no primes divide it, the number itself might be prime.
A foolproof way is to learn the first few primes above 53 by heart. Makes it easier.
References :
http://www.mathleague.com/help/wholenumbers/wholenumbers.htm#divisibilitytests
One simple algorithm is to find the square root of the number and then consider all the primes less than or equal to that square root. Now divide the original number by each of those primes, continuing until you have either found a division with a remainder of 0 or until you’ve exhausted your list of prime factors. If you never get a 0 remainder, the number is prime. In your example, the square root is between 14 and 15, so you must try trial division by (at most) 2,3,5,7,11,and 13. The last such division proves that 221 is composite, as you already know. There are much more efficient algorithms for larger primes, but the mathematical machinery for implementing them is considerably more complex.
References :