An isprime(n) function

[sneekula]

I need a function that returns True or False if an integer n is a prime. Any 'high speed' thoughts?

[Dani]

http://www.daniweb.com/code/search.php?query=prime

[mawe]

sneekula, I don't want to sound rude, but your one-sentence-question-posts are annoying. Why don't you try to find the answer alone first? If you're stuck, post what you have tried and we will try to help you.

BTW: The internet is full of isprime functions in any language you can dream of. 2 minutes of googling, that's all you need to do ;)

[Dani]

Forget the googlling, doing a search for "prime" within our code snippets section landed a function that outputs a list of prime numbers in python :)

[mawe]

Forget the googlling,

You are absolutely right, a search should always start in our snippets section :) But, searching for prime python via Google, I found a link to a snippet here (on the second page). You see, Google is not that bad :)

[vegaseat]

Our snippet examples give you a list of primes. You could get a list of primes in the range of your numbers, and then see if your numbers are in it. For simplicity sake you can use this small function ...

# prime numbers are only divisible by unity and themselves
# (1 is not considered a prime number)
 
def isprime(n):
    '''check if integer n is a prime'''
    # range starts with 2 and only needs to go up the squareroot of n
    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True
 
# test ...
print isprime(29)    # True
print isprime(345)   # False
print isprime(8951)  # True

[jrcagle]

If you're looking to test really large numbers, here's an implementation of the Rabin-Miller probabilistic test:

def primes(n):
    """
primes(n) --> primes

Return list of primes from 2 up to but not including n.  Uses Sieve of Erasth.
"""

    if n < 2:
        return []

    nums = range(2,int(n))
    p = []

    while nums:
        new_prime = nums[0]
        p.append(new_prime)

        for i in nums[1:]:
            if i % new_prime == 0:
                nums.remove(i)
        nums.remove(nums[0])

    return p

def power_mod(a, b, n):
    """
power_mod(a,b,n) --> int

Return (a ** b) % n
"""
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b % 2 == 0:
        return power_mod(a*a, b/2, n) % n
    else:
        return (a * power_mod(a,b-1,n)) % n
    
def rabin_miller(n, tries = 7):
    """
rabin_miller(n, tries) --> Bool

Return True if n passes Rabin-Miller strong pseudo-prime test on the
given number of tries, which indicates that n has < 4**(-tries) chance of being composite; return False otherwise.

http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
"""
    if n == 2:
        return True
    
    if n % 2 == 0 or n < 2:
        return False
    
    p = primes(tries**2)

    # necessary because of the test below
    if n in p:
        return True
    
    s = n - 1
    r = 0
    while s % 2 == 0:
        r = r+1
        s = s/2
    for i in range(tries):
        a = p[i]
        
        if power_mod(a,s,n) == 1:
            continue
        else:
            for j in range(0,r):
                if power_mod(a,(2**j)*s, n) == n - 1:
                    break
            else:
                return False
            continue
    return True

I can't guarantee that the implementation is correct, although it has passed testing so far. Also, the RM test only gives a probability of primeness, not absolute certainty. However, with default settings one has a 0% chance of false positives and a 0.006% chance of a false negative.

Jeff

[wallars]

1 is not prime:

def isPrime(n):
        if n == 1:
            return 0
        else:
            for x in range(2,int(n**0.5)+1):
                if n%x == 0:
                    return 0
            return 1

Here is a shorter primeList:

primeList = lambda n: set([i for i in range(2,n)]) ^ set([i for i in range(2,n) for x in range(2,int(i**0.5)+1) if i%x == 0])