Estoy tratando de ejecutar el siguiente código simple:

import math
def is_prime(N):
    for i in range(2, int(math.sqrt(N))):
        if (N % i == 0) :
            print(str(N) + " is not prime")
            return False 
    print(str(N) + " is prime")
    return True

El objetivo es determinar si un número es primo (bastante simple). Sin embargo, no puedo hacer que este código funcione. Me las arreglé para señalar el problema en torno a las instrucciones int(math.sqrt(N)), pero no entiendo por qué no funcionará, ya que ejecutar int(math.sqrt(134)), por ejemplo, funciona bien para mí. ¿Hay algo mal que no pueda ver en este código?

También he llegado a cuestionar la viabilidad del compilador. Estoy usando Sublime Text 3 con el Python Builder predeterminado. ¿Quizás hay algo que estoy haciendo que está específicamente mal en Sublime Text?

EDITAR: Olvidé mencionar el problema. Cuando ejecuto is_prime(8) por ejemplo, devuelve 8 is prime. Pero no muestra ningún error en absoluto. Sin embargo, debe tenerse en cuenta que ejecutar is_prime(134) imprime 134 is not prime como se esperaba. Podría intentar un bucle for si alguien quiere.

0
LaX 1 sep. 2014 a las 19:36

2 respuestas

La mejor respuesta

Prueba esto:

import math
def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0 :
            return False 
    return True

range() se detiene antes de llegar al segundo número. En este caso, también desea probar ese número, por lo que desea redondear hacia abajo y luego agregar uno.


Versión más eficiente (mejora de velocidad x10 - x1000):

def memoise(func):
    memory = {}
    def wrapper(n):
        if n in memory:
            return memory[n]
        ret = func(n)
        memory[n] = ret
        return ret
    return wrapper

@memoise
def is_prime(n):
    if n <= 3:
        return n > 1
    if not n%2 or not n%3:
        return False

    for i in range(5, int(n**0.5)+1, 6):
        if not n%i or not n%(i+2):
            return False
    return True

Jugando en la intérprete:

>>> math.sqrt(8)
2.8284271247461903
>>> int(math.sqrt(8)) + 1
3
>>> for i in range(2, 2):
        print(i)

>>> for i in range(2, 3):
        print(i)

2
1
Scorpion_God 2 sep. 2014 a las 08:13

Reescribí algunas de las líneas en su programa haciéndolo un poco más eficiente. Su ciclo for itera sobre todos los números hasta la raíz de N. Si comienza verificando si el número% 2 == 0, puede excluir todos los números pares y solo verificar los números impares 3, 5, 7, ... .

import math
def is_prime(N):
    if(N == 2):
        print(str(N) + " is a prime")
        return True
    if((N % 2 == 0)or(N == 1)):
        print(str(N) + " is not prime")
        return False
    for i in range(3,int(math.sqrt(N))+1,2):
        if(N % i == 0):
            print(str(N) + " is not prime")
            return False
    print(str(N) + " is prime")
    return True
1
peanut_butter 1 sep. 2014 a las 16:08