[Tutor] Generate Prime Numbers

[Alan Gauld]

On 30/05/15 19:14, Mirage Web Studio wrote:

> 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,

I'm not surprised. You seem to have a talent for finding complex 
solutions to fairly simple problems :-)

> 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.

Yes, using built in data structures (implemented in highly
optimised C) will nearly always be faster than building
your own in interpreted Python.

> My query is does using classes slowed it or the python hardcoded
> algorithm for dicts was better?

See above.
classes are great for modelling concepts that are not available
in the language. But both numbers and collections are well
provided for in Python.

> if you had to implement the sieve algorithm how would u have done it.

Similarly to your dict approach but probably using lists.
After all lists are naturally indexed by numbers so using
a dict keyed by numbers doesn't add much value.

There are also a few tweaks you can do to improve efficiency
but you are pretty much there.

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

A class with no methods other than init() is usually a bad sign.
You should always think very carefully whether another data
structure might not be more suitable. The whole point of
objects is that you do things to them. That means you need
methods to make them useful.

> node=Number(2,None,None)

Note the extra work you make Python do to initialise a number
each time compared to just assigning a built-in integer object.

> 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:

Notice you now have a loop within a loop. If you  are
looking for speed that's another bad sign. Compare with
your dict version there are two loops but they are not
nested, they run one after the other (and the first one
could be avoided using a list)

>              for i in range (newprime):

And now you have a third nested loop. Oh dear!

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

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos