Detailed explanation of a simple method to determine prime numbers (prime numbers) in Python-Python Tutorial-php.cn

Detailed explanation of a simple method to determine prime numbers (prime numbers) in Python

高洛峰

Release： 2017-03-06 13:25:25

Original

4953 people have browsed it

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

Copy after login

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)] ]

Copy after login

Using python’s itertools module

from itertools import count 
def isPrime(n): m.sbmmt.com
  if n <= 1: 
    return False 
  for i in count(2): 
    if i * i > n: 
      return True 
    if n % i == 0: 
      return False

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

The results are as follows:

Copy after login

For more detailed explanations of simple methods for Python to determine prime numbers (prime numbers), please pay attention to the PHP Chinese website!