[Tutor] Generate Prime Numbers

[Mirage Web Studio]

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