440,629 Members | 1,222 Online
Need help? Post your question and get tips & solutions from a community of 440,629 IT Pros & Developers. It's quick & easy.

# Function to determinate whether a number is prime or not

 P: 16 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: Expand|Select|Wrap|Line Numbers 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

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

Expand|Select|Wrap|Line Numbers
1. def is_prime2(n):
2.     if n<=1:
3.         return False
4.     elif n in (2, 3, 5, 7):
5.         return True
6.     elif str(n)[-1] in ('0', '2', '4', '5', '6', '8'):
7.         return False
8.     elif n%3==0:
9.         return False
10.     elif n%7==0:
11.         return False
12.     else:
13.         for i in range(11, int(n**0.5)+1, 2):
14.             if not n%i:
15.                 return False
16.     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.
Expand|Select|Wrap|Line Numbers
1. if __name__ == '__main__':
2.     import timeit
3.     t = timeit.Timer("is_prime(2000097)", "from __main__ import is_prime")
4.     print t.timeit()
5.     t = timeit.Timer("is_prime1(2000097)", "from __main__ import is_prime1")
6.     print t.timeit()
7.     t = timeit.Timer("is_prime2(2000097)", "from __main__ import is_prime2")
8.     print t.timeit()

Using the number 2000097, the results were virtually identical:
Expand|Select|Wrap|Line Numbers
1. >>> 1.45488211364
2. 1.42580345757
3. 1.42388930047
4. >>> 1.4366972181
5. 1.44870719986
6. 1.42893746692
7. >>> 1.43660163505
8. 1.43026986126
9. 1.46972456191
10. >>> 1.44520062355
11. 1.4405034696
12. 1.42799974136
13. >>> 1.4306084289
14. 1.44109168939
15. 1.42320573522
16. >>>
Using the number 2000095, your original code failed miserably. Using 10 iterations instead of 1000000:
Expand|Select|Wrap|Line Numbers
1. >>> 2.48837116033e-005
2. 1.38539355502
3. 1.83635415283e-005
4. >>>
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'):`

5 Replies

 Expert Mod 2.5K+ P: 2,851 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: Expand|Select|Wrap|Line Numbers >>> 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! Nov 25 '10 #2

 P: 16 Thank you, but I forgot a part of the code. In the end it says: Expand|Select|Wrap|Line Numbers return a Nov 25 '10 #3

 P: 16 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. Nov 25 '10 #4

 Expert Mod 2.5K+ P: 2,851 Good for you Gonzalo. Too bad the results aren't correct. I reworked your code somewhat: Expand|Select|Wrap|Line Numbers 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. Expand|Select|Wrap|Line Numbers 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: Expand|Select|Wrap|Line Numbers >>> 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: Expand|Select|Wrap|Line Numbers >>> 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'):` Nov 26 '10 #5

 P: 16 ooooooohh Thank you VERY much, I owe you one, that code is a piece of gold. Thank you Nov 26 '10 #6