Home > Article > Backend Development > Detailed explanation of a simple method to determine prime numbers (prime numbers) in Python
Prime numbers are also called prime numbers. Refers to a natural number greater than 1 that is not divisible by other natural numbers except 1 and the integer itself. Prime numbers play an important role in number theory. Numbers greater than 1 but not prime are called composite numbers. 1 and 0 are neither prime nor composite numbers. Prime numbers are two concepts that are opposite to composite numbers. The two constitute one of the most basic definitions in number theory. There are many world-class problems based on the definition of prime numbers, such as Goldbach's conjecture. The Fundamental Theorem of Arithmetic proves that every positive integer greater than 1 can be written as a product of prime numbers, and that the form of this product is unique. The important point of this theorem is that 1 is excluded from the set of prime numbers. If 1 is considered a prime number, then these strict formulations have to impose some restrictions. A few days ago, a friend occasionally asked Python how to determine a prime number. I checked online and summarized several methods for Python scripts to determine whether a number is a prime number:
1. Using python’s mathematical functions
import math def isPrime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True
2. Single-line program to scan prime numbers
from math import sqrt N = 100 [ p for p in range(2, N) if 0 not in [ p% d for d in range(2, int(sqrt(p))+1)] ]
Using python’s itertools module
from itertools import count def isPrime(n): www.php.cn if n <= 1: return False for i in count(2): if i * i > n: return True if n % i == 0: return False
3. Two methods without using modules
Method 1:
def isPrime(n): if n <= 1: return False i = 2 while i*i <= n: if n % i == 0: return False i += 1 return True
Method 2:
def isPrime(n): if n <= 1: return False if n == 2: return True if n % 2 == 0: return False i = 3 while i * i <= n: if n % i == 0: return False i += 2 return True
eg: Find the prime number (prime number) between 20001 and 40001
Since it can only be divided by 1 or itself, it means that there are only two times when the remainder is 0, the code is as follows:
#!/usr/bin/python L1=[] for x in xrange(20001,40001): n = 0 for y in xrange(1,x+1): if x % y == 0: n = n + 1 if n == 2 : print x L1.append(x) print L1
The results are as follows:
20011 20021 20023 20029 20047 20051 20063 20071 20089 20101 20107 20113 20117 20123 20129 20143 20147 20149 20161 20173 ….
For more detailed explanations of simple methods for Python to determine prime numbers (prime numbers), please pay attention to the PHP Chinese website!