Thread: 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?

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 , then if 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 (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.

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?

Carrefull, The sieve of Eratosthenes is efficient if you want all the primes below a given number ( vs ).

But not if you want to know if one number is prime or not ( vs ).

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].)

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?

Sieve of Atkin