Results 1 to 6 of 6

Math Help - Help with prime numbers

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    300

    Exclamation Help with prime numbers

    Hi, I need helping with coming up with the most efficient algorithm to check if a number is a prime number

    Code:
    def is_prime(n):
        n*=1.0
        if (n%2==0 and n!=2 or n%3==0 and n!=3) or n<2:
            return False
        for b in range(1,int((n**0.5+1)/6.0+1)):
            if n%(6*b-1)==0:
                return False
            if n %(6*b+1)==0:
                return False
        return True
                
    def prime(max_num, row, start):
        r_check = 0
        my_file = open("datafile.txt", "w")
        for num in range(start,max_num+1):
            r_check += 1
            if r_check > row:
                my_file.write("\n")
                r_check = 1    
            if is_prime(num):          
                my_file.write("1")
            else:
                my_file.write("0")
        my_file.close()
    This code I am pretty sure that it works.

    This is a code i found on the internet, it puts in a file, 0 for not prime and 1 for prime. Does anyone know of a faster algorithm? or a way to simplify it?

    I'm not asking for code here, but I guess just the algorithm written in steps.

    But if you could write the code, that would be awesome.

    Thanks


    Also whats the pattern for prime numbers?
    If you check this out

    The image is compressed, its actually 900x900, so if you want to see a clearer image, save the image, then zoom in.

    This is an animation i made, each frame is a square grid, where each blue pixel is a prime and black pixel isnt prime.
    each frame gets a bigger grid, this is because the first grid
    is a
    1x1 square, then
    4x4 square, then
    9x9
    16x16
    25x25
    36x36
    49x49
    .
    .
    .
    .
    900x900
    and each grid starts from the top left.

    the grid is like this

    1, 2, 3, 4, 5, 6, 7,..., n
    n+1 ...................... 2n
    2n+1.......................
    3n+1.......................
    ...............................
    .................................
    ...................................
    n(n-1)+1 ................n^2
    in the animation's case, n is 1, 2, 3, 4, ..., 30

    for each number, if its a prime, its represented as a blue pixel, otherwise its a black pixel.

    Does anyone see a pattern?
    Last edited by Sneaky; July 27th 2011 at 08:33 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Re: Help with prime numbers

    Hi,
    the method you are using is very, very inefficient. Your code is performing an enhanced version of trial division, which is one of the slowest algorithms known.

    Now, there are two types of algorithms to determine the primality of an integer:
    - Deterministic algorithms, that can prove that an integer is prime, but are usually quite slow
    - Probabilistic algorithms, that assert that an integer is "probably" prime with arbitrary probability, and are very fast

    All deterministic primality testing algorithms require more information about the integer to be able to work (usually the prime factorization of the integer minus 1), except two: trial division and AKS. The former is horribly slow, and the latter is a relatively recent algorithm which is "reasonably fast", but is a real hassle to implement (let's say it's not your average algorithm in terms of complexity)

    The probabilistic ones work as follows: you give them the number to check, and a parameter which describes how accurate the algorithm is. In return the algorithm either outputs COMPOSITE, which guarantees that the integer is not prime, or outputs PROBABLY PRIME, which means that the integer is likely to be prime within bounds described by the parameter. These algorithms are comparatively quite simple to implement, and really fast. Of course the drawback is that they can potentially identify a composite number as a prime, but more on that a bit below. Here is an example of one of the first probabilistic algorithms: Fermat's algorithm. It's based on the fact that if \gcd(a, p) = 1, then a^{p - 1} \equiv 1 \pmod{p} if p is prime - but this doesn't mean composite integers can't exhibit the same behavior. Thus you can construct an algorithm:

    INPUT n (number to check for primality), k (accuracy parameter)
    for k iterations, do
    ..choose a random number "a" between 2 and p - 2
    .. if a divides p, output COMPOSITE
    ..compute a^(p - 1) mod p
    ..if the result is different from 1, output COMPOSITE

    output PROBABLY PRIME (this happens if the integer made it through the loop)

    Now here's the catch with this algorithm - apart from the random aspect of it, there is a certain class of integers known as Carmichael numbers, which will pass the test regardless of "a". And unfortunately, those numbers are not prime.

    Fortunately this motivated the invention of several improved algorithms, and the pinnacle of probabilistic primality testing is called Miller-Rabin. While it is not much more complicated, it has the benefit of being substantially more accurate, and (more importantly) that there is no number that can fool this test. Now about the accuracy parameter k, with Miller-Rabin it means that if you let it run "k" times (refer to the loop in the pseudocode above), then the probability that a composite number "slips through" and is flagged as prime is roughly 4^{-k} (in the case of Miller-Rabin - it varies among algorithms). For practical purposes, this means that after 30 or so iterations, the probability that the algorithm made a mistake it actually lower than the probability of your hardware itself making a mistake, thus giving a fairly appreciable guarantee that the algorithm will be reliable. And of course, it is very fast (testing a number with several thousand digits should take much less than a minute).

    You can look up the algorithm here for a more in-depth description, and there are hundreds if not thousands of code snippets available for virtually every language.

    Hope I didn't confuse you too much, but if you are looking for an all-around solution to quickly check if any given integer is prime, Miller-Rabin is your friend.

    -----

    For your second question, look up Ulam's Spiral, which your images are a transform of. Essentially a guy called Ulam noted that prime numbers, when discretized over a two-dimensional space, tend to exhibit patterns (such as tending to line up on specific diagonals/etc..), and no one knows how to explain it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    300

    Re: Help with prime numbers

    I found a much faster algorithm on the internet
    Code:
    def eratosthenes(n):
           sieve = [ True for i in range(n+1) ]
           def markOff(pv):
                  for i in range(pv+pv, n+1, pv):
                         sieve[i] = False
           markOff(2)
           for i in range(3, n+1):
                  if sieve[i]:
                         markOff(i)
           return [ i for i in range(2, n+1) if sieve[i] ]
    this is a modified Sieve of Eratosthenes
    Sieve of Eratosthenes - Wikipedia, the free encyclopedia

    Also for the images, so really we should create different kinds of images (different patterns) until we see something that can be turned into an equation?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2011
    Posts
    27

    Re: Help with prime numbers

    Carrefull, The sieve of Eratosthenes is efficient if you want all the primes below a given number ( O(n\log\log n) vs O(\sum_{2\leq i\leq n}\lfloor \sqrt i \rfloor)).

    But not if you want to know if one number is prime or not ( O(n\log\log n) vs O(\sqrt n)).

    So, if you search an algorithm to test one number, don't do the sieve. There is some very efficient algorithm like Miller-Rabin as proposed. (I heard about an algorithm, maybe Miller-Rabin, whose probability that it gives a number prime which is actually not is less than the probability that a cosmic particle hits your computer and changes a 0 into a 1 in the processor [and so distorts the result].)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    300

    Re: Help with prime numbers

    So it turns out that i actually wanted to get list of primes below a certain number, instead of checking if its prime. But anyways I think this algorithm should be the fastest. Also I was thinking of arranging the numbers in different patterns to see if anything surprising comes out. I already tried putting them in a grid in order, but no surprises there, ulans spiral did the spiral and no surpirses there, what other things can I try?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Re: Help with prime numbers

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prime Numbers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: November 17th 2011, 07:39 AM
  2. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  3. prime numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 3rd 2010, 11:28 AM
  4. prime numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 15th 2008, 10:47 PM
  5. Prime numbers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: August 7th 2008, 10:16 AM

Search Tags


/mathhelpforum @mathhelpforum