On 2015-05-29 11:18 PM, Alan Gauld wrote:
On 29/05/15 16:28, George wrote:
Below is a sample code i created.
Can i better it any way?
Of course. There is always improvements that can be made.
But in your case there are quite a few!
def IsDivisibleBy3(number):#string variable
v=0
for c in number:
v=v+int(c)
if v%3==0:
return True
else:
return False
def IsDivisibleBy3(number):#string variable
return not int(number) % 3
def IsDivisibleBy7(number):#string variable
See above, but maybe better still
def isDivisibleByN(number, N):
return not int(number)%N
def IsPrime(number):
Google for the "sieve of eratosthenes"
Or look it up on wikipedia.
That will give one of several possible
improvements to your algorithm.
primelist=[]
for i in range (11,200000,2):
number=str(i)
print "checking ",i
if IsPrime(number):
Note, you are starting with a number, then converting
it to a string then in your functions converting it
back to a number.
That's crazy!
Also where do you store the primes less than 11?
ie. 1,3,5,7
HTH
Hello,
I thank u all for the replies. I have checked sieve of Eratosthenes
and have at first devised a solution using class-object, thinking it
easier, but it proved to be slower than my basic algorithm which i
submitted earlier, results were my algorithm processed 100 thousand
numbers in 80 or so sec but class based algorithm produced same result
in about 230 sec. After putting some thought i used dict for a change
with the sieve method and am able to produce primes for 1 million nos in
about 10 sec, which is better than both earlier algorithms. I am
submitting both.
My query is does using classes slowed it or the python hardcoded
algorithm for dicts was better?
and
if you had to implement the sieve algorithm how would u have done it.
Thank u
George
---------------------
class based algorithm
---------------------
import time
starttime=time.time()
class Number:
def __init__(self,number,p=None,n=None):
self.no=number
self.marked=None
self.p=p
self.n=n
node=Number(2,None,None)
start=node
counter=1
for i in range(3,110000):
counter+=1
newnode=Number(i,node)
node.n=newnode
node=newnode
node=start
while start != None:
if start.marked==True:
start=start.n
continue
else:
newprime = start.no
print ("\nNewPrime",newprime,"\nMarking no:")
tmpnode=start
while tmpnode !=None:
for i in range (newprime):
tmpnode=tmpnode.n
if tmpnode==None:
break
if tmpnode==None:
break
#print ( tmpnode.no, end=" ")
tmpnode.marked=True
start=start.n
print ("primes")
counter=0
while node!=None:
if not node.marked:
counter+=1
print(node.no)
node=node.n
print("--- %s seconds ---" % (time.time() - starttime), counter)
---------------------------
dict based algorithm
-------------------------
import time
starttime=time.time()
max=6000000
nodict={}
for i in range(2,max):
nodict[i]=0
for no in sorted(nodict.keys()):
x=no+no
while x<max:
nodict[x]=1
x+=no
counter=0
for no in sorted(nodict.keys()):
if nodict[no]==0:
counter+=1
print ("prime",no)
print("--- %s seconds ---" % (time.time() - starttime), counter)
---
This email has been checked for viruses by Avast antivirus software.
http://www.avast.com
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
