prime number

[lostinpython]

I'm having trouble writing a program that figures out a prime number.
Does anyone have an idea on how to write it? All I know is that n > 2
is prim if no number between 2 and sqrt of n (inclusivly) evenly
divides n.

 

[Tim Leslie]

I'm having trouble writing a program that figures out a prime number.
Does anyone have an idea on how to write it? All I know is that n > 2
is prim if no number between 2 and sqrt of n (inclusivly) evenly
divides n.

This sounds remarkably like a homework problem, so I'm not going to
give you a full answer. Perhaps if you could be more specific about
which part's giving you trouble we could help you out with that.

If it finding square roots? is it checking for divisibility? is it
getting the loop to run through correctly? Is it some other problem?

Tim

 

[Mike Meyer]

I'm having trouble writing a program that figures out a prime number.
Does anyone have an idea on how to write it? All I know is that n > 2
is prim if no number between 2 and sqrt of n (inclusivly) evenly
divides n.

How about this (untested):

import sys
import subprocess

primes = subprocess.Popen(["primes", sys.argv[1], sys.argv[1]],
stdout=subprocess.PIPE).stdout.readlines()
if primes:
print sys.argv[1], "prime"
else:
print sys.argv[1], "not prime"

Seriously, this sounds like a homework assignment. Google for "sieve
of eratosthenes". The BSD "primes" program I used in the above is an
implementation of that in C.

If it isn't a homework assignment, and you're honestly in such, then
you should know there's been a lot of research in this area, because
primes are important in cryptographic applications. Once again, google
is a good place to start on looking for recent research on the subject.

<mike

 

[lostinpython]

It is a homework assignment from a book but not for a class. I'm
trying to teach my self some basic programming before I have to take it
in college. If I show enough understanding of the subject, my advisor
will let me forgo Intro. to Programming and go into Intro. to C++.
What civil engineers need with all this programming is beyond me. We
have to learn another language to program our CADD software, which I
find much easier than this. But needless to say, I'm stumped on this
problem. I keep ending up in a never ending loop.

Shanna

I'm having trouble writing a program that figures out a prime number.
Does anyone have an idea on how to write it? All I know is that n > 2
is prim if no number between 2 and sqrt of n (inclusivly) evenly
divides n.

How about this (untested):

import sys
import subprocess

primes = subprocess.Popen(["primes", sys.argv[1], sys.argv[1]],
stdout=subprocess.PIPE).stdout.readlines()
if primes:
print sys.argv[1], "prime"
else:
print sys.argv[1], "not prime"

Seriously, this sounds like a homework assignment. Google for "sieve
of eratosthenes". The BSD "primes" program I used in the above is an
implementation of that in C.

If it isn't a homework assignment, and you're honestly in such, then
you should know there's been a lot of research in this area, because
primes are important in cryptographic applications. Once again, google
is a good place to start on looking for recent research on the subject.

<mike

 

[Brian van den Broek]

lostinpython said unto the world upon 2005-05-30 02:50:

It is a homework assignment from a book but not for a class. I'm
trying to teach my self some basic programming before I have to take it
in college. If I show enough understanding of the subject, my advisor
will let me forgo Intro. to Programming and go into Intro. to C++.
What civil engineers need with all this programming is beyond me. We
have to learn another language to program our CADD software, which I
find much easier than this. But needless to say, I'm stumped on this
problem. I keep ending up in a never ending loop.

Shanna

Hi Shanna,

Since you are just beginning, I'd like to recommend the tutor list
<http://mail.python.org/mailman/listinfo/tutor>. It is not that
newcomers are not welcome here. But the folks who populate the tutor
list are particularly good at answering neophytes' questions at the
level.

Since you've got some code together, even though it isn't doing what
you want, you've already got a decent start for getting help. Post the
question and the code to the tutor list and I'd not be surprised if
you will soon be well on your way to solving your problem.

Best,

Brian vdB
Who owes much of what he knows about Python to the tutor list.

 

[phil]

What civil engineers need with all this programming is beyond me.

One of my best friends and expartner and top civil-structural
engineers in the country (he built Dallas Reunion Arena and many
other complex structures) was an ace programmer in many languages.

He was not willing to just accept the results of canned packages,
he wanted to know where the answers came from and make software
that made sense to his engineers.

I presume you are young and if you wish to be an engineer and not
a salesman you must be eaten up with the desire to know
"How Stuff Works". Computers are ubiquitous in engineering
and if you want to be the best, learn how they work.

 

[Rocco Moretti]

But needless to say, I'm stumped on this
problem. I keep ending up in a never ending loop.

I've been told that the trick with recursion/iteration is to always
determine what your ending condition is first, and then construct the
body of the recursion/loop to reach that ending condition eventually. If
you post the specific code which is giving you problems, people here can
point out why you're missing the exit.

 

[Dale Hagglund]

lostinpython> I'm having trouble writing a program that figures
lostinpython> out a prime number. Does anyone have an idea on how
lostinpython> to write it?

[I can't quite tell from your posts what your level of programming
knowledge is, so I've aimed low. If this was wrong, please accept my
apologies. --rdh]

It's not quite clear precisely what the problem is. Do you want to
find all primes less than some number N, or find the prime
factorization of some input number, or something else altogether? Are
there any other constraints? Ie, does the program have to be
recursive?

I'm going to assume that you want to find all primes less than N, and
that are no constraints on the form of the program.

First, pretend you have a function called "is_prime". It will look
something like this:

def is_prime(n):
# return True if n is prime, False otherwise
# magic goes here

If we had this function, the our main program would look something
like this:

N = 20
for n in range(1, N+1):
if is_prime(n):
print n

NOTE: range(1,N+1) returns a list of numbers from 1 to N inclusive.

The question now is how to fill in the missing part of is_prime. In
your original post, you noted that n>2 is prime if no number between 2
and sqrt(n) inclusive divides into n evenly.

This tells us that we have to test a list of possible factors for
divisibility into n. Ignoring, for a little while, how we figure out
the possible factors, we can now expand is_prime as follows:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
for i in possible_factors:
# if i divides n, n isn't prime
# if no i divided into n, ie, we fell out of the loop,
# n is prime

The possible factor i divides into n if n % i == 0. Once we've
decided that n is or isn't prime, we can just return True or False
respectively. Adding these details:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
for i in possible_factors:
if n % i == 0:
return True
return False

The final step is to figure out the list of possible factors. By the
definition, this is the list of integers from 2 to the integer value
of sqrt(n), inclusive. To get this list, we can use the range
function again, assuming that sqrt(n) to compute the square root for
us. The list of possible factors is given by

range(2, int(sqrt(n)) + 1)

The final trick to is to get the definition of sqrt. It turns out
that this function is defined in the math module. Adding the bit of
syntax needed to access the sqrt function, we have:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True

Put together with the main program above, this will print out a list
as follows:

1
2
3
5
7
11
13
17
19

However, there's a slight problem here. By definition, 1 is not a
prime. We could fix this a couple of ways. Either we could change
the main program not to start its range with 1, or we can fix
is_prime. The latter is simple:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
if n == 1:
return False
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True

Another algorithm mentioned in the followups to your posting is the
Sieve of Eratosthenes, named for its ancient Greek discoverer. You
can find a description of the Sieve in many places on the web. Trying
to implement it might be a good next step.

Dale.

 

[Dale Hagglund]

Sigh ... one of my intermediate versions of is_prime() returns True if
the n is *not* prime, and false otherwise. The final version is
correct, though.

Dale.

 

[Mikael Olofsson]

What civil engineers need with all this programming is beyond me. We
have to learn another language to program our CADD software, which I
find much easier than this.

According to my experience, almost every engineer - civil or not - uses
programming at least occationally. So every engineering education
program should involve at least some programming.

/Mikael Olofsson

Universitetslektor (Senior Lecturer [BrE], Associate Professor [AmE])
Linköpings universitet

 

[Cameron Laird]

.
.
.

If it isn't a homework assignment, and you're honestly in such, then
you should know there's been a lot of research in this area, because
primes are important in cryptographic applications. Once again, google

.
.
.
There's been a lot of research in this area because some minds
burn to grasp the beauty of number theory, and can't stop think-
ing of Number despite blindness, hunger, family, political
oppression, and the other frailties to which humans are prone.

 

[Cameron Laird]

It is a homework assignment from a book but not for a class. I'm
trying to teach my self some basic programming before I have to take it
in college. If I show enough understanding of the subject, my advisor
will let me forgo Intro. to Programming and go into Intro. to C++.
What civil engineers need with all this programming is beyond me. We
have to learn another language to program our CADD software, which I
find much easier than this. But needless to say, I'm stumped on this

.
.
.
What's the crack about first place being a paid weekend vacation
in Philadelpha, and second place five days? Without knowledge of
the particulars of your situation, "Intro. to C++" sounds to me
more like punishment than incentive.

And I like C++.

One important instinct for your programming career is sensitivity
to "easier". I strongly suspect, though, that there are real
values in "basic programming" that your "CADD software" has not
yet taught you.

 

[Mike Meyer]

If it isn't a homework assignment, and you're honestly in such, then
you should know there's been a lot of research in this area, because
primes are important in cryptographic applications. Once again, google

.
There's been a lot of research in this area because some minds
burn to grasp the beauty of number theory, and can't stop think-
ing of Number despite blindness, hunger, family, political
oppression, and the other frailties to which humans are prone.[/QUOTE]

Good point. Similar reasons seem to cause a lot of software to get
written.

<mike