Question

Please please please help me with Problem set 1! I don't know what to do when it comes to computing the 1000th prime... If anyone wants to be amazing, can they explain it maybe? Thanks!

Answer 1

Ok, so the first thing you should do is building the algorithm. Not in code, in text. What do you want to do? Let's make it easy and say you want the 10th prime. How can you separate this problem?

Answer 2

I would take a test number, and see if it's prime by dividing by the prime components (2, 3), and if it's prime print it and add it to a list of primes to check the next number.

Answer 3

x = 3
count = 1

while count < 1000:
for x in range(1, x+1):
for y in range(1, x):
if y % x == 0:
break
else: x = x + 1
count = count + 1

I wrote this. It doesn't work, but it seems like it might have the write idea? Please help anyway you can :)

Answer 4

Ok, my first step would be this:

Given an number x, check if it is prime.

Also, check the definition of a prime number: "A natural number (i.e. 1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it has exactly two positive divisors, 1 and the number itself".


This is a list of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173.

You should start with the smaller ones (2,3,5,7,11) as tests, and then try with some bigger numbers.

So first write a code that tells you: Hey, this number is prime! And then focus on the second part of the problem (finding the nth prime)

Answer 5

x = raw_input("Number: ")
x = int(x)
isPrime = True

for y in range(2, x):
if x%y == 0:
isPrime = False
break
if isPrime == True: print "Your number is prime"

I wrote this, and it works for all numbers I've tested except for squares of primes, but it prints "Your number is prime" multiple times... Don't know why... Do you have any way to remedy this? Sorry for all the questions, I'm way new to this... Thanks for all your help!

Answer 6

The if isPrime == True: print "Your number is prime" is inside the for, it should be outside :)

Answer 7

In general, what they want is for you to divide by numbers to see if you get a remainder or not. If there is a remainder, it did not divide in and therefore it might be prime. If there is not a remainder, it is not prime.

Some tips:
You do not need to test even numbers, so you can start at 3 and work up. Just remember to adjust your count because you are skipping 2 and only need to find 999 more primes.

If you skip even numbers, you do not need to divide by even numbers. See, anything divisible by 10, 44, or 186 is also divisible by 2.

You only need to teest half the numbers below a number... well... it is actually less than that, but let me talk about the logic. No number will divide evenly by a number that is more than half of it. So you can eliminate a ton of testing by setting the upper bounds of every test to n/2 where n is the number being tested.

Answer 8

Thank you for helping me! I'm actually falling in love with cs because of this challenging problem! (and it's not even supposed to be that hard! ;P) can't wait to continue

Answer 9

I figured it out guys! Thanks for the help!

Answer 10

It was nothing :)