Isprime Function for Python Language

isPrime Function for Python Language

Of many prime number tests floating around the Internet, consider the following Python function:

def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  # since all primes > 3 are of the form 6n ± 1
  # start with f=5 (which is prime)
  # and test f, f+2 for being prime
  # then loop by 6. 
  f = 5
  while f <= r:
    print('\t',f)
    if n % f == 0: return False
    if n % (f+2) == 0: return False
    f += 6
  return True    

Since all primes > 3 are of the form 6n ± 1, once we eliminate that n is:

1. not 2 or 3 (which are prime) and
2. not even (with n%2) and
3. not divisible by 3 (with n%3) then we can test every 6th n ± 1.

Consider the prime number 5003:

print is_prime(5003)

Prints:

 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True

The line r = int(n**0.5) evaluates to 70 (the square root of 5003 is 70.7318881411 and int() truncates this value)

Consider the next odd number (since all even numbers other than 2 are not prime) of 5005, same thing prints:

 5
False

The limit is the square root since x*y == y*x The function only has to go 1 loop to find that 5005 is divisible by 5 and therefore not prime. Since 5 X 1001 == 1001 X 5 (and both are 5005), we do not need to go all the way to 1001 in the loop to know what we know at 5!

---

Now, let's look at the algorithm you have:

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

    return True

There are two issues:

1. It does not test if n is less than 2, and there are no primes less than 2;
2. It tests every number between 2 and n**0.5 including all even and all odd numbers. Since every number greater than 2 that is divisible by 2 is not prime, we can speed it up a little by only testing odd numbers greater than 2.

So:

def isPrime2(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
        if n%i==0:
            return False    

    return True

OK -- that speeds it up by about 30% (I benchmarked it...)

The algorithm I used is_prime is about 2x times faster still, since only every 6th integer is looping through the loop. (Once again, I benchmarked it.)

---

Side note: x**0.5 is the square root:

>>> import math
>>> math.sqrt(100)==100**0.5
True

---

Side note 2: primality testing is an interesting problem in computer science.

Function to check if number x is prime in python

Problem 1: The problem is range(n, x-1).

If your input is 2 or 3, range(2, x-1) will be an empty list since the second parameter of range is exclusive.

Since you're only returning inside the for loop and it never gets there, it returns None (i.e. it returns nothing).

Problem 2: Aside from never entering the for loop if x = 2 or x = 3, your code has some issues.

As you've written it, it will return in the first iteration. Certainly, if x % n == 0 you know x is not prime and can return False. But even if n is not a factor of x, you still have to check the other potential factors.

You should return True outside of the for loop, not inside it.

Solution:

if x == 2: return True
if x%2 == 0 or x < 2: return False
for n in range(3, x/2, 2):
  if x % n == 0:
    return False
return True

Python function to check if number is prime

def isprime(n):
    return (all([False for i in range(2,n) if n % i == 0 ]) and not n < 2)
    
print (isprime(0))
print (isprime(1))
print (isprime(2))
print (isprime(3))
print (isprime(9))
print (isprime(10))
print (isprime(13))

Output:

False
False
True
True
False
False
True

Or:

def isprime(n):

    if n < 2: return False

    for i in range(2, n):
        if n % i == 0:
            return False
    else:
        return True

Validate if input number is prime

The sympy.isprime() is a built-in function under the SymPy module and can be utilized for checking of possible prime numbers. It is a direct function and returns True if the number to be checked is prime and False if the number is not prime.

>>> import simpy
  
>>> sympy.isprime(8)

False

>>> sympy.isprime(11)

True

or else define a function like this

>>> def isPrime(k):
    
    # 1 is not prime number
    if k==1:
        return False

    # 2, 3 are prime
    if k==2 or k==3: 
        return True

    # even numbers are not prime
    if k%2==0: 
        return False

    # check all numbers till square root of the number , 
    # if the division results in remainder 0
    # (skip 2 since we dont want to divide by even numbers)

    for i in range(3, int(k**0.5)+1, 2):
        if k%i==0:
            return False

    return True

>>> print(isPrime(13))

True

>>> print(isPrime(18))

False

checking prime number in python

Your problem is that the else part of your for-loop is wrong. You print "the number is prime" every time a division check fails, not just at the end.

I added an isPrime boolean that tracks if a single check failed. Only if none of them fail, you can print that the number is prime.

num = int(input("please enter the number you want to check\n"))

if num > 1:
    isPrime = True
    for i in range(2, num):
        if (num % i) == 0:
            print("the number is not prime")
            print(str(i) + " times " + str(num//i) + " is "+ str(num))
            isPrime = False
            break
    if isPrime:
        print("the number is prime")
elif(num == 1):
    print("the number is not prime")
else:
    print('enter a positive value')

You can simplify that even more, with a construct of python called for-else (credits to @TheGamer007):

num = int(input("please enter the number you want to check\n"))

if num > 1:
    for i in range(2, num):
        if (num % i) == 0:
            print("the number is not prime")
            print(str(i) + " times " + str(num//i) + " is "+ str(num))
            break
    else:
        print("the number is prime")
elif(num == 1):
    print("the number is not prime")
else:
    print('enter a positive value')

It works because Python's for-loops can have an else: following, which only triggers if you don't break out of the loop.

This might be exactly what you were trying to do. In that case, all you did wrong was your indentation.

Also, from an algorithmical point of view, there are much better ways to check. A first simple improvement is that you don't need to check range(2,num), but only range(2, int(math.sqrt(num))+1)

Print series of prime numbers in python

You need to check all numbers from 2 to n-1 (to sqrt(n) actually, but ok, let it be n).
If n is divisible by any of the numbers, it is not prime. If a number is prime, print it.

for num in range(2,101):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num)

You can write the same much shorter and more pythonic:

for num in range(2,101):
    if all(num%i!=0 for i in range(2,num)):
       print (num)

As I've said already, it would be better to check divisors not from 2 to n-1, but from 2 to sqrt(n):

import math
for num in range(2,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print (num)

For small numbers like 101 it doesn't matter, but for 10**8 the difference will be really big.

You can improve it a little more by incrementing the range you check by 2, and thereby only checking odd numbers. Like so:

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print (num)

Edited:

As in the first loop odd numbers are selected, in the second loop no
need to check with even numbers, so 'i' value can be start with 3 and
skipped by 2.

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
        print (num)

---

Related Topics