Question

I'm stuck on problem set 1 still, but I've made some progress. It's the one about printing the 1000th prime number. So far all I have is a prime number generator based on an input number. Here's the code:

for num in range (1,80): #80 can be any number
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
print num

If anyone knows how I can turn this into a function that prints a particular number, i.e. the 1000th prime, I would really appreciate it.

Answer 1

Wrap another loop around it.
num_primes = 0
target = 1000 #can be any number
while num_primes < target:
your code, but unsead of print num, num_primes++

Then print num after it drops out of the inner loop.

Answer 2

I took your advice and applied it to the code, but it's not quite right. I feel I'm not fully understanding the structure of loops because I feel this is a simple mistake; but nevertheless, I would appreciate it if you could point me in the right direction. Here is the new code:

def primeNums():
num_primes = 0
target = 1000
while num_primes < target:
for num in range (1,8000):
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
num_primes += 1
print "Prime #1000 is: ", num

The main problem now is that it doesn't print the 1000th prime. It just prints the last prime in the range given. Basically, 'num_primes' is incrementing, but it doesn't kick out of the loop when it gets to 1000, it just keeps going. Essentially it's not communicating with the 'num_primes' variable at the beginning of the function.

Answer 3

Did you look at a list of 1000 primes vs. your 1000 primes? See if you can find any errors towards the last group when you do 1000 of them. If there are, then the issue is in finding primes. On the other hand, if you find 1000 fine but you output something else when searching for the 1000th, then the error is in when to stop, start, or something like that.

Answer 4

num_primes increments by one for each prime, so that part is correct. However, it does not stop when it gets to 1000, so it just keeps going until it gets to the end of the range. So if the range is 10, it will print 7, or if its, 10000000, it will print the last prime in that range. I need to make it so that the num_primes stops when it gets to 1000. Do I need to move the num_primes variable inside the loop? Because of right now, it's always 0.

Answer 5

Well, I thnk you need a way to get the prime out of the loop. So a way to get a copy of num out. See, the loop you are stuck in is the inner loop.

Answer 6

I don't know if you're familiar with the website, pythontutor, but it's an interactive code/stack iterator. I used it and saw the same thing as you i.e. I'm stuck in the inner loop. The problem seems to come down to the for loop with the range of x (in my case 8000). It iterates through this loop for that set amount of time no matter what number of primes there is. I want the code to break out of the loop when it gets to:

if prime:
primes += 1

Instead, it just goes back to the top of the while loop and never checks to see if primes is less than the target. Is there anyways I can make the code check the parameter num_primes < target?

Answer 7

Well, because you pasted your code here without ``` above and below, if I copy it, it collapses onto one line, so I have not tried it... I know there are ways to not use 8000. I have a couple sitting here. But I have not played with yours.

Some sort of variable and keeping track of which prime was found last is generally what would be used.

Answer 8

`Sorry, I didn't know you couldn't use my code. That would have made this much easier.

```
def primeNums():
num_primes = 0
print "num_primes =" ,num_primes
target = 1000
while num_primes < target:
for num in range (1,8100):
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
num_primes += 1
print "Prime #1000 is: ", num
```
Let me know if that helps

Answer 9

Use ` the one on ~ on a separeate line.... yah, like that.

Answer 10

Hmm, well, it finds 1, which is not a prime number. They start at 2.

Answer 11

And it seems to be finding them that many times, not just finding the 1000th.

Answer 12

If you change the range from (1,x), to (2,x) that should fix that problem. But I'm still working on getting it to stop at 1000. Do I need to take out a loop, add a loop, add a variable or something to make this work properly? Perhaps my code can't do what I want with the way I have it set up. Maybe it needs a major alteration in order to get it on the right track for printing only the 1000th prime.

Answer 13

I think so. See what I get with this?

```
def primeNums():
num_primes = 0
print "num_primes =" ,num_primes
target = 100
last_prime = 2
now_testing = 3
while num_primes < target:
for num in range (last_prime,now_testing):
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
num_primes += 1
last_prime = num
print "Found:" , num
now_testing += 1
# print "Prime #1000 is: ", num

primeNums()
```

Answer 14

I find 100 primes, but there are huge repeats.

Answer 15

Ah, take a look at this:
```
def primeNums():
num_primes = 0
print "num_primes =" ,num_primes
target = 1000
last_prime = 0
now_testing = 3
low_limit = 2
while num_primes < target:
for num in range (low_limit,now_testing):
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
num_primes += 1
last_prime = num
print "Found:" , num, " num_primes:" ,num_primes
low_limit += 1
now_testing += 1
# print "Prime #1000 is: ", num

primeNums()
```

Answer 16

Maybe this will help. This is the bare code that just prints all the prime numbers up to a specified number.

```
for num in range (2,81): #81 is arbitrary
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
print num
```

Answer 17

Wow, I'm impressed. It works beautifully. I'm going to dissect it and try to fully understand the code and thought process behind it, but I would appreciate any insight you could give me. What are some of the things you thought that contributed to you writing this code? I guess, if you could just explain your thought process and kind of walk me through the code, that would clear up some of the confusion and help me understand this better.

Thank you so much for you help e.mccormick. You have helped me tremendously and encouraged me to keep trying. I really appreciate your help; the world needs more people like you :)

Answer 18

Well, for one thing, see how limit the area being tested? I don't test everything. There is probably one more loop in there than is needed, but ut us working at this point. Also, I made a way to get the prime out. Last prime. That will be able to be printed instead of everything else.

Answer 19

Here is another to look at:
http://dpaste.com/hold/1394767/

Another user did that, and I did some tweaks.

Answer 20

There was no reason for all the static assignments they did, and the code is made for 3.x, but many of the principals will be the same. Oh, and the new print command from 3 might work fine in 2.7.5.

Answer 21

Here are a few principals that can make a prime finder work faster:

1: After dividing by 2, you only need to divide by odd numbers.
2: You only need to test half the values, well, less, but half is an easy number. If it can't be divided by any number in the first half, it is prime.
3: If you try dividing by 2 and 3 to start, you may be able to test only the first third. Similarly, 4 is covered by 2 and then 5 might make it so you only need to check the first 5th. I think this is true, but never wrote it to see.

The less math done, the faster it runs!

Answer 22

I've modified it slightly, do do the exact specifications for the assignment. (Print only the 100th prime.) All I did was remove a few print statements, rename the function and re word the output. Hopefully this can serve as a reference for future students stumped by this assignment. Here is the code:

```
def printPrime(n): #n is the desired prime; so if you want the 7th prime, n=7
num_primes = 0
target = n
last_prime = 0
now_testing = 3
low_limit = 2
while num_primes < target:
for num in range (low_limit,now_testing):
prime = True
for i in range (2, num):
if (num % i == 0):
prime = False
if prime:
num_primes += 1
last_prime = num
low_limit += 1
now_testing += 1
print "Prime #", n, "is:", num
```

Answer 23

Yah. Examples can be very helpful. However, it is also good to work on finding a solution. \(\ddot\smile\)

Answer 24

Hi there,

I am also new to programming. Here is my solution to this problem. I am doing this just for fun.

Code:
http://dpaste.com/hold/1396354/



Both programs can reach the same conclusion. Mine runs faster.

The 1000th prime number is 7919
Time used is 0.0310001373291

Prime # 1000 is: 7919
Time used is 5.18700003624

Answer 25

For some reason, the code figure did not show up properly. It appears OK on dpaste.com.