Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Yubing_Wang

  • one year ago

Hello Guys, I'm a very beginner in computer science.I have trouble solving this problem--find the 1000th prime. i have tried a lot of time,but can not write working code. the following is one of the code i tried, still not working, can anyone help me with the finding prime problem? thanks candidate=3 a=[] prime=[] for i in range(2,candidate): b=candidate%i c=a.append(b) if 0 in c: candidate+=2 else: final_prime=prime.append(candidate) candidate+=2 while len(final_prime)=999: Final_prime=[2]+final_prime print Final_prime

  • This Question is Open
  1. JonnyTruelove
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Im just as lost as you bro. But even tho its wrong your code has inspired me to think in a different direction so thank you. I think somewhere you need to multiply n**0.5 + 1. I dunno where yet lol but maybe it will help you.

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

    i worked out the code about the prime number, as following: candidate=3 final_prime=[2] while len(final_prime)<1000: result=True for i in range(2,candidate): if(candidate%i==0): result=False if result==True: prime=candidate final_prime.append(prime) candidate+=2 print final_prime,final_prime[999] even though it's not perfectly efficient, it worked. if you have more effient way to solve this problem,please sent me the code, thanks.

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

    Nice job getting your code working :) One thing you could try to get a bit more efficient code is by breaking (using the `break` keyword) from the loop after you set result to False. That way, the number that are higher won't be checked. Antoher thing you can have a look at is the Sieve of Eratosthenes (see: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) and try to implement that in python.

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

    yes,you are right, thank you

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

    here is a prime test that is actually pretty fast: http://dpaste.com/1004316/

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

    thank you

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

    One thing that everybody seems to forget is that any non-prime number can be factored into prime numbers. If you implement that fact, your program will run fast.

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

    what does that even mean rsmith? any non prime number can be factored into prime numbers? how will that make the program run fast?

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

    don't you still have to perform primality tests to generate prime numbers? those tests consume the time. http://dpaste.com/1010237/

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

    Memoization.

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

    @rsmith6559 - so you are talking about an algorithm that uses previously found primes in the primality tests. do you have an example?

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

    primes = [ 2, 3 ] testNum = 5 numberOfPrimes = 10000 while( len( primes ) < numberOfPrimes ): for i in xrange( 0, len( primes ) ): if( testNum % primes[i] ): if( i == ( len( primes ) - 1 )): primes.append( testNum ) else: break testNum += 2

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

    @rsmith6559 - the algorithm you posted takes 70 times longer to find the 10,000th prime than one using the test i posted. http://dpaste.com/1011884/

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

    I tuned the code a bit: primes = [ 2, 3 ] testNum = 5 numberOfPrimes = 10000 while( len( primes ) < numberOfPrimes ): for i in xrange( 0, len( primes ) ): if( testNum % primes[i] ): if( primes[i] * primes[i] > testNum ): primes.append( testNum ) break else: break testNum += 2 I'm getting 0.67 second execution time.

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

    still 20% slower http://dpaste.com/1012984/

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

    I don't see how you can be getting 20 second times: [zeus@stamRSMITH:~/Desktop]$ time ./ps1.py The 10000th prime is: 104729 real 0m0.688s user 0m0.662s sys 0m0.017s [zeus@stamRSMITH:~/Desktop]$ time ./ps1.py The 10000th prime is: 104729 real 0m0.674s user 0m0.656s sys 0m0.016s [zeus@stamRSMITH:~/Desktop]$ time ./ps1.py The 10000th prime is: 104729 real 0m0.676s user 0m0.657s sys 0m0.016s [zeus@stamRSMITH:~/Desktop]$ time ./ps1.py The 10000th prime is: 104729 real 0m0.678s user 0m0.657s sys 0m0.016s [zeus@stamRSMITH:~/Desktop]$ time ./ps1.py The 10000th prime is: 104729 real 0m0.679s user 0m0.659s sys 0m0.017s [zeus@stamRSMITH:~/Desktop]$ time ./ps1.py The 10000th prime is: 104729 real 0m0.674s user 0m0.656s sys 0m0.016s

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

    http://docs.python.org/2.7/library/timeit.html those times are for 100 executions - finding the 10000th prime 100 times on my machine your algorithm takes 25. seconds for 100 executions - which is still 20% slower than the algorithm from the wikipedia article. i made a couple of readability changes to your code at lines 7, 8, 9 - http://dpaste.com/1013998/ now yours is 25% faster - cool

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

    I'm not saying that my code is the fastest possible. Originally, I was just commenting on a mathmatical fact that nobody was taking advantage of. My purpose for mentioning it was that the brute force algorithms, with thought, could be replaced with more efficient algorithms. Certainly a lesson to be taken from ps1 (Problem Set 1).

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

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

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.