How to Count Prime Numbers in a Python Script?

[mateomy]

x=0
y = raw_input("""Up to what number would you like to locate primes?: """)
for i in range(int(y)):
x = x + 1
if x%2 and x%3 and x%5 and x%7:
print x, '--> PRIME'
elif x==2 or x==3 or x==5 or x==7:
print x, '--> PRIME'
elif x==1:
print x
else:
print xI've been on break for the last week and a half and I thought I would spend my time learning Python. I wrote this little script earlier tonight that simply prints out a list of integers within a user specified range and identifies which of them are prime. What I want to do but can't seem to find any documentation on is to have the script count the occurrences of the primes and echo a "There were (blank) number of primes within your specified interval." I have no idea where to look for that sort of thing. I don't want an answer but I would like someone to point me in the direction I need to be going in.

As always,
Thanks.

P.S. This does work, I just want to make it 'better'.

 

[chiro]

Hey mateomy.

Have you considered saving results to some array and then processing the array later?

 

[mateomy]

Hey mateomy.

Have you considered saving results to some array and then processing the array later?

I've never really done that before. I'm only loosely familiar with arrays in Python as I've only been at this about a week or so. I'm interested in learning though...

 

[chiro]

Well basically an array can be dynamic (i.e. you determine its size from a variable at runtime) or static (you specify a fixed size that the program uses and it is fixed).

Because computers have lots of memory, it's really not a big issue to allocate a huge array because not only do we have lots of memory (RAM), but it's getting faster as well.

Take a look at something like this:

http://pentangle.net/python/handbook/node39.html

Basically the idea is to create an array and then store all your stuff in the array and then you can process it later to get whatever information out that you want after you've done your prime routine above.

So if you want say the first n items in your list, then just access your array and get the first ten items. You can then do whatever you want with those like print them to a file, or the screen (pretty much whatever you want).

If you do more and more programming, what you'll end up doing is you'll create functions that will take some data in and maybe spit some data back out and in this case if you get data out, you call a function which does its thing and then you take that data and do whatever you want with it (maybe give it to another function for instance).

 

[mateomy]

Great! I'll take a look at that.

Thank you very much. I'll post back with new questions.

 

[mateomy]

I'm confused how I'd get this output piped into an array.

 

[uart]

What I want to do but can't seem to find any documentation on is to have the script count the occurrences of the primes and echo a "There were (blank) number of primes within your specified interval." I have no idea where to look for that sort of thing.

Hi mateomy, your program only works up to a maximum count of 120, due to only testing for divisibility with a limited number primes. To make the program more general (able to resolve larger primes) you need to store (and compare against) a "list" of primes currently found, rather than just working with that fixed set of "2,3,5,7".

That being said, with your current program it is an extremely simple matter of just incrementing a counter to achieve what you want. For example,

x=0
count = 0
y = raw_input('Up to what number would you like to locate primes? : ')
for i in range(int(y)):
  x = x + 1
  if (x%2 and x%3 and x%5 and x%7 and x<>1) or x==2 or x==3 or x==5 or x==7:
    print x, '--> PRIME'
    count += 1
  else:
    print x

print 'There were ',count,' primes in your range.'

I haven't really tried to fix your code (except for not printing "1" as a prime), I've just compacted it a little to make it easier to read.

Note the the line "count += 1" is essentially just shorthand for "count = count + 1". And btw, please use "code" "/code" tags (in square brackets) to preserve your formatting.

 

[mateomy]

Awesome! It's nice to be able to see someone with more experience put out a code that's a little more compact and efficient. I'm trying to get a handle on Python at a rudimentary level so I was pretty excited when it even ran. How does that count function work exactly?

 

[Borek]

Funny, last year I tried to learn something about Python, and program finding n primes was the first thing I did:

import math

primes = [2]

nth = 30

def prime(n):
   """Checks if number n is prime, using table of primes found earlier."""
   for p in primes[:int(math.sqrt(n))]:
      if n % p == 0:
         return False
   return True

i = 2
while len(primes) < nth:
   i = i+1
   if prime(i):
      print i
      primes.append(i)

n is hard coded, not asked for, but it doesn't change the idea.

 

[uart]

How does that count function work exactly?

It's so simple I was hoping it would be self explanatory

The variable "count" is initialized to zero at the start of the program and then incremented by one (in the loop) each time that a prime is found. The line "count += 1" is does the same thing as "count = count + 1", that is, it increments the counter.

 

[uart]

Funny, last year I tried to learn something about Python, and program finding n primes was the first thing I did:

import math

primes = [2]

nth = 30

def prime(n):
   """Checks if number n is prime, using table of primes found earlier."""
   for p in primes[:int(math.sqrt(n))]:
      if n % p == 0:
         return False
   return True

i = 2
while len(primes) < nth:
   i = i+1
   if prime(i):
      print i
      primes.append(i)

n is hard coded, not asked for, but it doesn't change the idea.

Thanks Borek. Hopefully that will give the OP some ideas on how to extend the program.

There's one little problem you might like to fix though. With the array slice in the line "for p in primes[:int(math.sqrt(n))]", you're effectively testing for divisibility up to the prime whos index in the list is \sqrt{n}, however you should in fact be testing elements whos values are less than \sqrt{n}. You see what I mean, the limit should be on the size of the prime, not on its index.

Actually the code should still work, since the prime counting function \pi(n) is asymptotic to n/\ln(n). And since \sqrt{n}/\ln(\sqrt{n}) \leq \sqrt{n} \leq n/\ln(n) for n>2 then your code should always test enough primes and shouldn't exceed the list bounds. Though in general it will test more primes than needed.

 

[Borek]

you're effectively testing for divisibility up to the prime whos index in the list is \sqrt{n}

Good point, thanks. It is just a proof I am not thinking in correct categories.

 

[mateomy]

Oh okay, now I that I see that the 'count' is within the code indent for the 'if' value it IS self explanatory. That's cool. Thanks for the pointers.

Borek, it is weird that you tried the same thing. Your code is much cleaner (not to mention further reaching) than mine, however.