Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I primality test

  1. Jul 1, 2017 #1
    Take for example 377 to test its primality. I will only test its divisibility with

    (3*5*7*....*125) (because 377/3=125.67, so here the multiplication series end with 125 ).

    377 will be able to divide it. (Since I know 377=13*29, i.e in the numerator 13 & 29 will be divided by 377, hence the total is divisible by 377.)

    If a number is a prime, then the above method will not be divisible.

    I am aware for very very big number, the multiplication series product will be enormously large. But isn't it, theoritically, it will work?


    Thanks.
     
  2. jcsd
  3. Jul 1, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can stop testing possible factors at ##\sqrt{377} \approx 19.4##. If there is a factor ##a## larger than 19.4, then there is also a factor ##b=377/a## smaller than 19.4.

    Theoretically you can test the primality of every number that way, yes. It gets impractical and there are faster ways, but it is possible.
     
  4. Jul 1, 2017 #3
    (3*5*....*19). 377 won't divide this. Because 377=13*29. Since it has no 29. 377 won't be able to divide it.

    Yes.
     
  5. Jul 1, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Huh? You are reversing the logic.

    You test if 377 is divisible by 2, 3, 5, ... up to 19.

    You can also test of 377 is a factor of 2*3*5*7*...*125 but that doesn't tell you anything.
    377 is a factor of that product. It is not a prime.
    4 is not a factor of that product. It is not a prime either.
     
  6. Jul 1, 2017 #5
    I didn't get that.

    For prime I will be only considering odd numbers. So I will not be taking 2 in the multiplication series.

    (3*5*7*...*125) are not divisible by 373 and 379. Since they are prime. Also 125 is a large number to multiply in the series. If we knew a number is not divisible by 3,5 and 7. The multiplication can be reduced to (3*5*7*...*53), since 379/7=54.14
     
  7. Jul 1, 2017 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    There is nothing special about 2.
    Which part is unclear?

    3*5*7*9*...*125 will have all non-prime numbers up to some large value as factor. So what?
    1849=432 should be the first non-prime which is not a factor of this large product.
     
  8. Jul 1, 2017 #7
    Ok, thats right. Because the product series has only one 43.
     
  9. Jul 1, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Exactly.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: primality test
  1. Failing tests (Replies: 2)

  2. Compositeness test (Replies: 6)

Loading...