Guest User

Untitled

a guest
Oct 2nd, 2012
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.65 KB | None | 0 0
  1. # you have 1 prime already, and the first prime is 2,
  2. # so we start checking from 3
  3. # I've also renamed variables to make it easier to read (imo)
  4. numPrimes= 1
  5. divisor = 2
  6. candidate = 3
  7. while numPrimes <= 1000:
  8.     result = candidate % divisor
  9.     if result > 0:
  10.         divisor +=1
  11.     elif result == 0:
  12.         if divisor == candidate:
  13.             print candidate
  14.             candidate +=1
  15.             numPrimes +=1
  16.             divisor =2
  17.         else:
  18.             candidate +=1
  19.             divisor = 2
  20.  
  21. # regardless of what happens in the if, you're setting the divisor to 2
  22. # and adding one to the candidate, so don't do it in the if
  23. # you no longer need the 'else'
  24. numPrimes= 1
  25. divisor = 2
  26. candidate = 3
  27. while numPrimes <= 1000:
  28.     result = candidate % divisor
  29.     if result > 0:
  30.         divisor +=1
  31.     elif result == 0:
  32.         if divisor == candidate:
  33.             print candidate
  34.             numPrimes +=1
  35.         candidate +=1
  36.         divisor = 2
  37.  
  38.  
  39. # because result is the outcome of a mod equation,
  40. # it will always be zero or positive
  41. # so make the elif and else
  42. numPrimes= 1
  43. divisor = 2
  44. candidate = 3
  45. while numPrimes <= 1000:
  46.     result = candidate % divisor
  47.     if result > 0:
  48.         divisor +=1
  49.     else:
  50.         if divisor == candidate:
  51.             print candidate
  52.             numPrimes +=1
  53.         candidate +=1
  54.         divisor = 2
  55.        
  56.  
  57. #result is only used in one place, so the variable isn't really necessary
  58. numPrimes= 1
  59. divisor = 2
  60. candidate = 3
  61. while numPrimes <= 1000:
  62.     if (candidate % divisor) > 0:
  63.         divisor +=1
  64.     else:
  65.         if divisor == candidate:
  66.             print candidate
  67.             numPrimes +=1
  68.         candidate +=1
  69.         divisor = 2
  70.  
  71. # you're essentially making two while loops in this code
  72. # this is what it looks like in separate loops
  73. numPrimes= 1
  74. candidate = 3
  75. while numPrimes <= 1000:
  76.     divisor = 2
  77.     while (candidate % divisor) > 0:
  78.         divisor +=1
  79.     if candidate == divisor:
  80.         print candidate
  81.         numPrimes+=1
  82.     candidate+=1
  83.  
  84.  
  85. # this rearrangement makes it easier to optimise
  86. numPrimes= 1
  87. candidate = 3
  88. while numPrimes <= 1000:
  89.     divisor = 2
  90.     isPrime = True
  91.     while divisor < candidate:
  92.         if candidate % divisor == 0:
  93.             isPrime = False
  94.         divisor += 1
  95.     if isPrime:
  96.         print candidate
  97.         numPrimes+=1
  98.     candidate+=1
  99.  
  100. # we know that for every divisor above the square root of anumber,
  101. # that number will have another divisor below the square root
  102. # so we check the smaller search space (below the square root).
  103. # we need to check the square root as well
  104. # just in case that number is the square of another prime
  105. from math import sqrt
  106. numPrimes= 1
  107. candidate = 3
  108. while numPrimes <= 1000:
  109.     divisor = 2
  110.     isPrime = True
  111.     while divisor <= sqrt(candidate):
  112.         if candidate % divisor == 0:
  113.             isPrime = False
  114.         divisor += 1
  115.     if isPrime:
  116.         print candidate
  117.         numPrimes+=1
  118.     candidate+=1
  119.  
  120. # if a number is divisible by 4, it's also divisible by 2.
  121. # the same property holds for all non-prime numbers
  122. # so you only need to check divisibility by prime numbers
  123. # this change provides support for storing and checking all primes
  124. # again, only primes below the sqrt!
  125. from math import sqrt
  126. primes = [2]
  127. candidate = 3
  128. while len(primes) <= 1000:
  129.     isPrime = True
  130.     for prime in primes:
  131.         if candidate % prime == 0:
  132.             isPrime = False
  133.         if prime > sqrt(candidate):
  134.             break
  135.     if isPrime:
  136.         print candidate
  137.         primes.append(candidate)
  138.     candidate+=1
  139.  
  140. # 2 is the only even prime number, so we don't need to check even numbers
  141. # we're also evaluating the sqrt of a number multiple times in a loop
  142. # it never changes, so we can store that in a variable to save extra processing
  143. from math import sqrt
  144. primes = [2]
  145. candidate = 3
  146. while len(primes) <= 1000:
  147.     isPrime = True
  148.     sqrtCandidate = sqrt(candidate)
  149.     for prime in primes:
  150.         if candidate % prime == 0:
  151.             isPrime = False
  152.         if prime > sqrtCandidate:
  153.             break
  154.     if isPrime:
  155.         print candidate
  156.         primes.append(candidate)
  157.     candidate+=2 #candidate can't be even for this to work
  158.  
  159. # these small optimisations can only go so far without changing
  160. # the method we use to calculate primes altogether
  161.  
  162. # The above method is called Trial Division.
  163. # It's probably the worst prime calculating method that is actually used.
  164.  
  165. # If you care about fast computation of LOTS of primes,
  166. # have a look at the Sieve of Eratosthenes
  167. # It's a good place to start.
Advertisement
Add Comment
Please, Sign In to add comment