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

Home

Backend Development

Python Tutorial

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

高洛峰

Mar 06, 2017 pm 01:25 PM

pythonprime numberprime numbers

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:

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

Statement

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn