Skip to main content

View Diary: Perhaps a simpler way to find out if a number is prime. (44 comments)

Comment Preferences

  •  Sorry 617 digit number (0+ / 0-)

     I am betting my way is faster than the way computer's find primes now by factoring out every possible number in a series of numbers to find out if a number is prime. my way you get rid of the three's and only multiply the primes of past  prime numbers not every possible number. I was hoping someone among the computer literate people here might be able to plug and chug my idea on a computer and test it.
        Still try my way with scratch paper and a calculator time yourself and have a friend try it the old way and see who wins:)

    •  That is not how computers factor numbers. They (2+ / 0-)
      Recommended by:
      rfall, crankyinNYC

      actually use some fairly advanced math such as the Number Field Sieve or even the older and less efficient Quadratic Sieve both of which are much faster than than your method assuming a very large number is being used (they aren't that efficient for small numbers though).

      Actually, the absolute fastest way to factor numbers is using Shor's algorithm but that requires a computer capable of storing information as both 1 and 0 at the same time until it is "observed" (i.e. a quantum computer).  Assuming  such a computer were built that was powerful enough, it could factor any number in polynomial time.

      There is no saving throw against stupid.

      by Throw The Bums Out on Mon Dec 05, 2011 at 01:44:36 PM PST

      [ Parent ]

      •  Can they find the primes (0+ / 0-)

        for a large series of numbers as quick as I can starting from 1?  I will check your links and study but without a computer I really can't test it however are these methods as easy as mine to use is my nest question.
             Since we don't have quantum computers yet I will look at the number sieve first. maybe a challenge is in order? My idea vs the number sieve with 2 humans using pen and paper.
             Nothing is known for sure of course until its computer tested.

        •  That is not what the number field sieve is (0+ / 0-)

          for.  It is for the problem of "given integer N, find all prime factors" which is generally the most common problem you would want to solve with such a method.  Also, the number field sieve is designed for numbers over 100 digits which makes a pencil and paper test impractical.  Also think about how you would parallelize your method as for practical usage it would have to be run in a computer cluster composed of many different computers working together.  Each computer would have several cores which would be the equivalent of having a thousand people working on it and coordinating their results.

          There is no saving throw against stupid.

          by Throw The Bums Out on Tue Dec 06, 2011 at 04:26:10 AM PST

          [ Parent ]

Subscribe or Donate to support Daily Kos.

Click here for the mobile view of the site