Function to determinate whether a number is prime or not

[Gonzalo Gonza]

Hello, I made a function to define whether a number n is prime or not. But I have two problems that will be described, but first let's go to the function:

def esprimo(n):
	m=str(n)
	if n<=1:
		a=False
	elif n==2:
		a=True
	elif int(m[-1])==(2 or 4 or 6 or 8 or 0 or 5):
		a=False
	elif n%3==0:
		if n!=3:
			a=False
		else: a=True
	elif n%7==0:
		if n!=7:
			a=False
		else: a=True			
	else:
		a=True
		check=11
		while check<n+1:
			if n%check==0:
				if n/check==1:
					pass
				else:
					a=False
			check+=2

However, it has two problems:
1. When the input is 8 the output is True. That's the only error, but I don't know why.
2. It's bad optimized, I want to know if there are things that I can omit, or a better way to define if a number is prime or not

Thank you

[bvdet]

Your function does not return anything. Use the return statement to return True if n is prime and False if n is not prime. Example using the return statement:

>>> def f(n):
... 	if not n%2:
... 		print "Number is divisible by 2"
... 		return True
... 	return False
... 
>>> f(5)
False
>>> f(12)
Number is divisible by 2
True
>>>

A somewhat efficient algorithm:
If n is less than 2, return False
If n is equal to 2, return True
If not n%2, return False

Start a for loop over for i in range( starting with 3, up to the square root of n in increments of 2.
If not n%i, return False

If it gets through all of the above, it's a prime number!

[Gonzalo Gonza]

Thank you, but I forgot a part of the code. In the end it says:

return a

[Gonzalo Gonza]

Also I proved your algorithm and its speed equation is t=1,0*10^-84 x^51,4 and mine was t=7,8*10^-26 x^16,23, so mine is faster.

[bvdet]

Good for you Gonzalo. Too bad the results aren't correct.

I reworked your code somewhat:

def is_prime2(n):
    if n<=1:
        return False
    elif n in (2, 3, 5, 7):
        return True
    elif str(n)[-1] in ('0', '2', '4', '5', '6', '8'):
        return False
    elif n%3==0:
        return False
    elif n%7==0:
        return False
    else:
        for i in range(11, int(n**0.5)+1, 2):
            if not n%i:
                return False
    return True

I compared the speed of the three functions using the timeit module. is_prime() is my original suggestion, is_prime1() is your original code, and is_prime2() is your code modified.

if __name__ == '__main__':
    import timeit
    t = timeit.Timer("is_prime(2000097)", "from __main__ import is_prime")
    print t.timeit()
    t = timeit.Timer("is_prime1(2000097)", "from __main__ import is_prime1")
    print t.timeit()
    t = timeit.Timer("is_prime2(2000097)", "from __main__ import is_prime2")
    print t.timeit()

Using the number 2000097, the results were virtually identical:

>>> 1.45488211364
1.42580345757
1.42388930047
>>> 1.4366972181
1.44870719986
1.42893746692
>>> 1.43660163505
1.43026986126
1.46972456191
>>> 1.44520062355
1.4405034696
1.42799974136
>>> 1.4306084289
1.44109168939
1.42320573522
>>>

Using the number 2000095, your original code failed miserably. Using 10 iterations instead of 1000000:

>>> 2.48837116033e-005
1.38539355502
1.83635415283e-005
>>>

The problem with your original code is where you check to see what the last digit is in the number. Instead of this:
elif int(m[-1])==(2 or 4 or 6 or 8 or 0 or 5):
It should be something like this:
elif str(n)[-1] in ('0', '2', '4', '5', '6', '8'):

[Gonzalo Gonza]

ooooooohh
Thank you VERY much, I owe you one, that code is a piece of gold.
Thank you