A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

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!

  • This Question is Closed
  1. osanseviero
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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?

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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 :)

  4. osanseviero
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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)

  5. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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!

  6. osanseviero
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  7. e.mccormick
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I figured it out guys! Thanks for the help!

  10. osanseviero
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    It was nothing :)

  11. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.