Loading ...
Sorry, an error occurred while loading the content.
 

Primality Testing

Expand Messages
  • Ronald Dwyer
    Lately I have been interested in primality testing: to determine whether a number, N, is prime or composite. From what I have thus far read, various tests have
    Message 1 of 3 , Sep 6, 2004
      Lately I have been interested in primality testing: to determine
      whether a number, N, is prime or composite.
      From what I have thus far read, various tests have strengths and
      weaknesses.
      Some tests are 100% correct, but it may take a long time to test,
      comprising hundreds of hours for a computer to test a 4,000 digit
      number.
      Other tests can give a quick response, but at the sacrifice of
      accuracy: sometimes a false answer is given.
      I was wondering if there a method yet to determine with 100% accuracy
      whether a number is prime or composite, in a quick amount of time.

      My thinking on the subject, for what its worth, is this:
      1. We can immediately say that numbers whose digits end in
      0,2,4,5,6,8 are composite.
      2. That leaves numbers ending with the digits 1, 3, 7, 9. Some of
      these numbers are prime, some are not. To sort these out is the hard
      part.
      3. Of the numbers that end in the digit 9, one thing we can do is
      this: if we 'cast out' that 9, and if the remaing digits are a
      multiple of 3, then, the original number, N, is a composite. For
      example, the following numbers are composite: 1239, 3339, 50109.
      4. One thing which I thought was a correct rule but not anymore: If
      you cast out the last digit 9, and then if you add 2 to the remaining
      digits: if you then have a a number whose first half of its digits
      are the same as its seocnd half, then that number is composite. To
      illustrate: take 209. cast out the 9; add 2 to the remaining digits,
      which will make 22. 209 is composite. Or take 319. Cast out the 9;
      add 2 to the digits, which will make 33. 319 is composite.
      This rule seems to work many times, but I have found at least one
      counterexample. So I give this caveat to save somebody else trouble.



      Best Regards,

      Ron Dwyer
    • Jud McCranie
      At 06:50 PM 9/6/2004, Ronald Dwyer wrote: 3. Of the numbers that end in the digit 9, one thing we can do is ... That is of very little help because it tells
      Message 2 of 3 , Sep 6, 2004
        At 06:50 PM 9/6/2004, Ronald Dwyer wrote:
        3. Of the numbers that end in the digit 9, one thing we can do is
        >this: if we 'cast out' that 9, and if the remaing digits are a
        >multiple of 3, then, the original number, N, is a composite. For
        >example, the following numbers are composite: 1239, 3339, 50109.

        That is of very little help because it tells if the number is divisible by
        3, so that rules out very few of the cases.
      Your message has been successfully submitted and would be delivered to recipients shortly.