Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Yubing_Wang

  • 3 years 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
    • 3 years 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
    • 3 years 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
    • 3 years 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes,you are right, thank you

  5. bwCA
    • 3 years 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thank you

  7. rsmith6559
    • 3 years 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
    • 3 years 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
    • 3 years 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Memoization.

  11. bwCA
    • 3 years 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
    • 3 years 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
    • 3 years 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
    • 3 years 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  16. rsmith6559
    • 3 years 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
    • 3 years 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
    • 3 years 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

Sign Up
Find more explanations on OpenStudy
Privacy Policy