By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,629 Members | 1,222 Online
Bytes IT Community
+ Ask a Question
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
  1. def esprimo(n):
  2.     m=str(n)
  3.     if n<=1:
  4.         a=False
  5.     elif n==2:
  6.         a=True
  7.     elif int(m[-1])==(2 or 4 or 6 or 8 or 0 or 5):
  8.         a=False
  9.     elif n%3==0:
  10.         if n!=3:
  11.             a=False
  12.         else: a=True
  13.     elif n%7==0:
  14.         if n!=7:
  15.             a=False
  16.         else: a=True            
  17.     else:
  18.         a=True
  19.         check=11
  20.         while check<n+1:
  21.             if n%check==0:
  22.                 if n/check==1:
  23.                     pass
  24.                 else:
  25.                     a=False
  26.             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
Nov 24 '10 #1

✓ answered by bvdet

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

I reworked your code somewhat:
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'):

Share this Question
Share on Google+
5 Replies


bvdet
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
  1. >>> def f(n):
  2. ...     if not n%2:
  3. ...         print "Number is divisible by 2"
  4. ...         return True
  5. ...     return False
  6. ... 
  7. >>> f(5)
  8. False
  9. >>> f(12)
  10. Number is divisible by 2
  11. True
  12. >>> 
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
  1. 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

bvdet
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
  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'):
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

Post your reply

Sign in to post your reply or Sign up for a free account.