473,573 Members | 2,768 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Little novice program written in Python

Hi, All.

I'm just getting my feet wet on Python and, just for starters, I'm coding some
elementary number theory algorithms (yes, I know that most of them are already
implemented as modules, but this is an exercise in learning the language idioms).

As you can see from the code below, my background is in C, without too much
sophistication.

What I would like is to receive some criticism to my code to make it more
Python'esque and, possibly, use the resources of the computer in a more
efficient way (the algorithm implemented below is the Sieve of Eratosthenes):

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#!/usr/bin/env python

n = int(raw_input() )
a = [i for i in range(0,n+1)]
a[1] = 0 # not a prime
prime = 1 # last used prime
finished = False

while (not finished):
prime = prime + 1
# find new prime
while prime*prime <= n and a[prime] == 0:
prime += 1
# cross the composite numbers
if prime*prime <= n:
j = 2*prime
while j <= n:
a[j] = 0
j += prime
else:
finished = True

# print out the prime numbers
i = 2
while i <= n:
if a[i] != 0:
print a[i]
i += 1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Thank you for any help in improving this program,

--
Rogério Brito : rbrito@{mackenz ie,ime.usp}.br : GPG key 1024D/7C2CAEB8
http://www.ime.usp.br/~rbrito : http://meusite.mackenzie.com.br/rbrito
Projects: algorithms.berl ios.de : lame.sf.net : vrms.alioth.deb ian.org
Jun 27 '08 #1
21 1382
What I would like is to receive some criticism to my code to make it more
Python'esque and, possibly, use the resources of the computer in a more
efficient way (the algorithm implemented below is the Sieve of Eratosthenes):
It looks like straight-forward code and is fine as it stands.
If you want to tweak it a bit, you can avoid using a flag like
"finished" by using a break-statement.
Raymond
Jun 27 '08 #2
Rogério Brito wrote:
Hi, All.

I'm just getting my feet wet on Python and, just for starters, I'm
coding some elementary number theory algorithms (yes, I know that most
of them are already implemented as modules, but this is an exercise in
learning the language idioms).

As you can see from the code below, my background is in C, without too
much sophistication.

What I would like is to receive some criticism to my code to make it
more Python'esque and, possibly, use the resources of the computer in a
more efficient way (the algorithm implemented below is the Sieve of
Eratosthenes):

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#!/usr/bin/env python

n = int(raw_input() )
a = [i for i in range(0,n+1)]
a[1] = 0 # not a prime
prime = 1 # last used prime
finished = False

while (not finished):
prime = prime + 1
# find new prime
while prime*prime <= n and a[prime] == 0:
prime += 1
# cross the composite numbers
if prime*prime <= n:
j = 2*prime
while j <= n:
a[j] = 0
j += prime
else:
finished = True

# print out the prime numbers
i = 2
while i <= n:
if a[i] != 0:
print a[i]
i += 1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Thank you for any help in improving this program,
Your Python is actually pretty good - if Raymond Hettinger pronounces it
OK then few would dare to disagree.

As for your English, though, the word you sought was "Pythonic" (not
that you will ever find such a word in Webster's dictionary). To suggest
that your code is Pythonesque would mean you found it farcical or
ridiculous (like a Monty Python sketch), which it clearly is not.

Another wrinkle you might consider is simply printing the primes out as
they are generated rather than doing the printing in a separate loop,
though whether that approach would be preferable in "real life" would
depend on the application, of course.

regards
Steve

PS: I think either my mailer or yours has mangled the indentation.
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/

Jun 27 '08 #3
On Apr 24, 11:09*pm, Dennis Lee Bieber <wlfr...@ix.net com.comwrote:
On Thu, 24 Apr 2008 21:31:15 -0300, Rogério Brito <rbr...@ime.usp .br>
declaimed the following in comp.lang.pytho n:
a = [i for i in range(0,n+1)]

* * * * Uhm... At least in 2.4 and earlier, range() returns a list.... No
need for the list-comp in that era... range() also begins with 0
>n = 5
a = range(n+1)
a
[0, 1, 2, 3, 4, 5]

* * * * So just

* * * * a = range(n+1)

could be used. Of course, if using a version where range() and xrange()
have been unified...
>c = list(xrange(n+1 ))
c
[0, 1, 2, 3, 4, 5]

--
* * * * Wulfraed * * * *Dennis Lee Bieber * * * * * * * KD6MOG
* * * * wlfr...@ix.netc om.com * * * * * * *wulfr...@besti aria.com
* * * * * * * * HTTP://wlfraed.home.netcom.com/
* * * * (Bestiaria Support Staff: * * * * * * * web-a...@bestiaria. com)
* * * * * * * * HTTP://www.bestiaria.com/
You're talking hardware-native, which machines don't guarantee.
Python can in another dimension of machine compatibility. Stacks are
hardware native, the location of an array is not. Python can retrieve
your stack in higher dimensions.

Fortunately, Python's community is sturdy against counterproducti vity
en masse, so it's okay to hairbrain it. Cover features of
improvements, though, and you might get a Bayes Net change to make and
courses to steer. The community values the flexibility of machine-
independency too.

However, real numbers are not integers, so opinion mass of integer
algorithms may favor C. But you just need micro-sales (and scales!)
to examine the future of Python. Welcome to our group.
Jun 27 '08 #4
Peter Otten wrote:
Rogério Brito wrote:

>i = 2
while i <= n:
if a[i] != 0:
print a[i]
i += 1

You can spell this as a for-loop:

for p in a:
if p:
print p

It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.
If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p
Cheers,
RB
Jun 27 '08 #5
On Apr 25, 5:44 pm, Robert Bossy <Robert.Bo...@j ouy.inra.frwrot e:
Peter Otten wrote:
Rogério Brito wrote:
i = 2
while i <= n:
if a[i] != 0:
print a[i]
i += 1
You can spell this as a for-loop:
for p in a:
if p:
print p
It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.

If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p
... at the cost of almost doubling the amount of memory required.
Jun 27 '08 #6
John Machin wrote:
On Apr 25, 5:44 pm, Robert Bossy <Robert.Bo...@j ouy.inra.frwrot e:
>Peter Otten wrote:
>>Rogério Brito wrote:

i = 2
while i <= n:
if a[i] != 0:
print a[i]
i += 1

You can spell this as a for-loop:

for p in a:
if p:
print p

It isn't exactly equivalent, but gives the same output as we know that a[0]
and a[1] are also 0.
If the OP insists in not examining a[0] and a[1], this will do exactly
the same as the while version:

for p in a[2:]:
if p:
print p


... at the cost of almost doubling the amount of memory required.
Indeed. Would it be a sensible proposal that sequence slices should
return an iterator instead of a list?

RB
Jun 27 '08 #7


Rogério Brito:
Hi, All.

I'm just getting my feet wet on Python and, just for starters, I'm coding some
elementary number theory algorithms (yes, I know that most of them are already
implemented as modules, but this is an exercise in learning the language idioms).

As you can see from the code below, my background is in C, without too much
sophistication.

What I would like is to receive some criticism to my code to make it more
Python'esque and, possibly, use the resources of the computer in a more
efficient way (the algorithm implemented below is the Sieve of Eratosthenes):
my variant of the sieve

def GetPrimes(N):
arr = []
for i in range(1,N+1):
arr.append(i)
#Set first item to 0, because 1 is not a prime
arr[0]=0
#sieve processing
s=2
while s < math.sqrt(N):
if arr[s-1] != 0:
j = s*s
while j <= N:
arr[j-1] = 0
j += s
s += 1
return [x for x in arr if x != 0]
Jun 27 '08 #8
also, i would recommend you to visit projecteuler.ne t
you can solve math tasks and then see how others have done the same.

you can fetch very good and pythonic solution there.

Jun 27 '08 #9
hellt <Do*********@gm ail.comwrites:
my variant of the sieve
Since you posted it, you are also looking for advice to improve your
code ;)
def GetPrimes(N):
arr = []
for i in range(1,N+1):
arr.append(i)
This is the same as:
arr = range(1, N+1)
!-)
#Set first item to 0, because 1 is not a prime
arr[0]=0
#sieve processing
s=2
remove this line
while s < math.sqrt(N):
for s in xrange(2, int(math.sqrt(N ))+1):
if arr[s-1] != 0:
if arr[s-1]:
j = s*s
remove this line
while j <= N:
for j in xrange(s*s, N+1, s):
arr[j-1] = 0
j += s
remove this line
s += 1
remove this line
return [x for x in arr if x != 0]
return filter(None, arr)
Altogether now:

def getprimes(N):
arr = range(1, N+1)
arr[0] = 0
for s in xrange(2, int(math.sqrt(N ))+1):
if arr[s-1]:
for j in xrange(s*s, N+1, s):
arr[j-1] = 0
return filter(None, arr)

It's the same, but it looks a bit less like the litteral translation
of some C code.
Lastly, the lines:

for j in xrange(s*s, N+1, s):
arr[j-1] = 0

from above can be condensed using extended slices:

arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1)

(If I can count correctly)

Giving the following, slightly shorter and probably faster:

def getprimes(N):
arr = range(1, N+1)
arr[0] = 0
for s in xrange(2, int(math.sqrt(N ))+1):
if arr[s-1]:
arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1)
return filter(None, arr)
If it was me, I would include 0 in the array, giving the slightly simpler:

def getprimes(N):
arr = range(N+1)
arr[1] = 0
for s in xrange(2, int(math.sqrt(N ))+1):
if arr[s]:
arr[s*s : N+1 : s] = [0] * (N/s - s + 1)
return filter(None, arr)

(I think)

This all needs to be tested.

--
Arnaud
Jun 27 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
3418
by: Ron Stephens | last post by:
I posted to my web site a fun little program called merlin.py today. Please keep in mind that I am a hobbyist and this is just a little hack, if you look at the code you will see that it is still possible to write spaghetti code, even with Python. I apologize, and I do intend to clean up the code, but it may take awhile. For now it works, with...
76
8778
by: Alan Connor | last post by:
-- Alan C this post ends with w q From K&R: #include <stdio.h> main()
2
1157
by: bole2cant | last post by:
I just received my free VB.NET package from MS, and can't figure out how to Save As. I loaded a sample program and made a bunch of changes to it and wanted to save it without overwriting the original sample. The only place I could Save As was the one place I didn't want to save it. Even with a different name it tells me I have to save it in...
4
3041
by: vagrantbrad | last post by:
I'm using python 2.4 running on Fedora Core 4. I have written a python program called ipscan.py that checks the external ip address of my cable internet connection, and on change, will update the dns records at my dns provider, zoneedit. So basically, I've setup dynamic dns using python. Once the ip compare and/or update is complete, I log...
1
1019
by: The Confessor | last post by:
For my previous project, I stored persistent data from Structures in three different Random Access files between sessions, but that's not likely to be an option with this one... For starters, I'm trying to become more 'class-aware' with my code in this project. I've declared those global variables which will be written to and read from...
29
16479
by: 63q2o4i02 | last post by:
Hi, I'm interested in using python to start writing a CAD program for electrical design. I just got done reading Steven Rubin's book, I've used "real" EDA tools, and I have an MSEE, so I know what I *want* at the end of this; I just have never taken on a programming task of this magnitude. I've seen that some are using python as a utility...
3
2387
by: Darius | last post by:
Hello, there is an NMEAParserDemo application written in VC++ avaliable for download from http://www.visualgps.net/Papers/NMEAParser/NMEAParserDemo%20Project.zip. Source code in VC++ is provided, unfortunately this application features no logging option. My intention is to add data logging option to let me read processed lat, lon, alt,...
4
1389
by: Chelonian | last post by:
I'm considering trying to learn Python for a specific reason, and hoped the group might help me get a sense for whether it would be worth my time. The situation... Me: total beginner w/ a sense of programming basics and 1 week familiarizing myself with Python world. Use WinXP. Got Python 2.5. Fooled around in IDLE, made "hello world!"...
1
2993
by: TwistedSpanner | last post by:
Hello all, For the record I am a complete java novice. I have to write a program to generate/output to screen 10 simple maths question and output a final score . The question is as follows Random number, Random operator (+ or -) random number. I have written the program but cannot make the random operator work. Can anyone help? My...
0
7746
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7668
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8179
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7736
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
6358
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5556
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5258
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
1
1269
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
999
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.