Maison  >  Article  >  développement back-end  >  Explication détaillée d'une méthode simple pour déterminer les nombres premiers (nombres premiers) en Python

Explication détaillée d'une méthode simple pour déterminer les nombres premiers (nombres premiers) en Python

高洛峰
高洛峰original
2017-03-06 13:25:255083parcourir

Les nombres premiers sont également appelés nombres premiers. Fait référence à un nombre naturel supérieur à 1 qui n'est pas divisible par d'autres nombres naturels sauf 1 et l'entier lui-même. Les nombres premiers jouent un rôle important en théorie des nombres. Les nombres supérieurs à 1 mais non premiers sont appelés nombres composés. 1 et 0 ne sont ni des nombres premiers ni des nombres composés. Les nombres premiers sont deux concepts opposés aux nombres composés. Les deux constituent l'une des définitions les plus fondamentales de la théorie des nombres. Il existe de nombreux problèmes de classe mondiale basés sur la définition des nombres premiers, comme la conjecture de Goldbach. Le théorème fondamental de l'arithmétique prouve que tout entier positif supérieur à 1 peut s'écrire comme un produit de nombres premiers et que la forme de ce produit est unique. Le point important de ce théorème est que 1 est exclu de l’ensemble des nombres premiers. Si 1 est considéré comme un nombre premier, alors ces formulations strictes doivent imposer certaines restrictions. Il y a quelques jours, un ami a parfois demandé à Python comment déterminer les nombres premiers. J'ai vérifié en ligne et résumé plusieurs méthodes de scripts Python pour déterminer si un nombre est premier :

1. fonctions mathématiques

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. Programme sur une seule ligne pour scanner les nombres premiers

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

Utiliser le module itertools de python

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

Deux méthodes sans utiliser de modules
Méthode 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

Méthode 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

 
Exemple : Trouver les nombres premiers (nombres premiers) entre 20001 et 40001
Comme il ne peut être divisé que par 1 ou par lui-même, cela signifie qu'il n'y a que deux fois où le le reste est 0 , le code est le suivant :

#!/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

Le résultat est le suivant :

20011
20021
20023
20029
20047
20051
20063
20071
20089
20101
20107
20113
20117
20123
20129
20143
20147
20149
20161
20173
….

Plus Python détermine les nombres premiers (nombres premiers), veuillez faire attention au site Web PHP chinois pour des articles connexes détaillés !


Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn