Funcion isprime() [Python]

[isseu]

Aprendiendo Python y tratando de descubrir alguna forma por mi solo para sacar comprobar si un numero es primo cree esta funcion que compare con otras que aparecen en la red y puedo decir que es mas rapida y gasta menos recursos que las demas
Sacar Primeros 100 digitos Primos:

Código (python) [Seleccionar] Expandir

#/usr/bin/env phyton
import math

def isprime(a):
d = True
if a==0 or a==1:
 d=False
b = 2
c = math.sqrt(a)
while b <= c and d == True:
 if a%b==0:
  d = False
 b+=1
return d

a=1
while(a<100):
if(isprime(a)==True):
 print str(a)
a+=2

[pucheto]

Pone a+=2 en vez de a+=1.. los primos nunca van a ser pares...
De todas formas la diferencia es nula, apenas cambia en 0.001 el tiempo

[isseu]

cualquier milesima vale
muy buena idea

[pucheto]

Estaba al pedo y me tente

Código (python) [Seleccionar] Expandir

import math
import time

def isprime(a):        #verifica si a es primo
   d = True
   if a==0 or a==1:
       d=False
   b = 2
   c = math.sqrt(a)
   while b <= c and d == True:
       if a%b==0:
           d = False
       b+=1
   return d


def loop():            #mientras el tiempo transcurridosea menor q 5 busca primos
   a=1
   count = 0
   now = 0
   start = time.time()

   while((now-start)<5):
       if(isprime(a)==True):
           count += 1
       now = time.time()
       a+=2
   return count

def main():            #Llama 3 veces a loop() y hace un promedio de los resultados
   runs = 3
   s = 0
   for i in range(0,runs):
       s += loop()
       print "Run",i+1
   s = s/runs
   print "Score: ",s

print "Cerra todos los programas q tengas abiertos..."
raw_input("Despues presiona cualquier tecla...")
main()



39210 primos en 5 segundos! (CPython 2.6)
Haber q resultados les da a los demas..

[pucheto]

43752 primos en 5 seg si uso IronPython... curioso este ultimo... (el iron python hace alguna optimizacion just in time?)

[h0oke]

Mmm

aver te dejo esta función para que la compares, es c++ pero puedes adaptarla ya que no se python...

Código (c) [Seleccionar] Expandir

bool EsPrimo(int x)
{
     int PD=2;
     while((PD <= X/2)&&(X%PD!= 0)//*
     {
           PD++;
     }
     if((PD > X/2)&&(X!=1)){return 1;}//*
}

*X/2 tiene que ser división ENTERA.

[h0oke]

Al parecer leyendo algo de código, el mio quedaría algo asi:

Código (python) [Seleccionar] Expandir

def EsPrimo(x):
     e=FALSE
     PD=2
     while PD<=x//2 and  x%PD!=0:
          PD=PD+1
     if PD>x//2 and x!=1:
          e=TRUE
     return e

[pucheto]

no pongas PD<=(x/2)... combiene mas usar PD <= math.sqrt(x)
Los números compuestos son divisibles por algún primo menor q su raiz cuadrada.

Para no calcular la raiz tantas veces podes almacenarla en una variable auxiliar.

[isseu]

muy bueno el code pucheto, estaba aprendiendo Python y no encontraba mucha info sobre lo de Time,
¿SOLO 17818? (con programas abiertos)

[link87]

mi versión:

Código [Seleccionar] Expandir


import time, math

def calcularPrimos(tiempo):
   primos = [2]
   start = now = time.time()
   n = 3
   while (now-start) < tiempo :
       es_primo = True
       raiz = math.sqrt(n)
       for p in primos:
           if p > raiz :
               break
           if (n % p) == 0 :
               es_primo = False
               break
       if es_primo:
           primos.append(n)
       now = time.time()
       n += 2
   return primos

pr = calcularPrimos(5) #calculamos primos durante 5 segundos
print len(pr)


89684 primos en 5 segundos. En linux con firefox abierto.

Edit: por cierto, como se hace para que sombree la sintaxis