Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # you have 1 prime already, and the first prime is 2,
- # so we start checking from 3
- # I've also renamed variables to make it easier to read (imo)
- numPrimes= 1
- divisor = 2
- candidate = 3
- while numPrimes <= 1000:
- result = candidate % divisor
- if result > 0:
- divisor +=1
- elif result == 0:
- if divisor == candidate:
- print candidate
- candidate +=1
- numPrimes +=1
- divisor =2
- else:
- candidate +=1
- divisor = 2
- # regardless of what happens in the if, you're setting the divisor to 2
- # and adding one to the candidate, so don't do it in the if
- # you no longer need the 'else'
- numPrimes= 1
- divisor = 2
- candidate = 3
- while numPrimes <= 1000:
- result = candidate % divisor
- if result > 0:
- divisor +=1
- elif result == 0:
- if divisor == candidate:
- print candidate
- numPrimes +=1
- candidate +=1
- divisor = 2
- # because result is the outcome of a mod equation,
- # it will always be zero or positive
- # so make the elif and else
- numPrimes= 1
- divisor = 2
- candidate = 3
- while numPrimes <= 1000:
- result = candidate % divisor
- if result > 0:
- divisor +=1
- else:
- if divisor == candidate:
- print candidate
- numPrimes +=1
- candidate +=1
- divisor = 2
- #result is only used in one place, so the variable isn't really necessary
- numPrimes= 1
- divisor = 2
- candidate = 3
- while numPrimes <= 1000:
- if (candidate % divisor) > 0:
- divisor +=1
- else:
- if divisor == candidate:
- print candidate
- numPrimes +=1
- candidate +=1
- divisor = 2
- # you're essentially making two while loops in this code
- # this is what it looks like in separate loops
- numPrimes= 1
- candidate = 3
- while numPrimes <= 1000:
- divisor = 2
- while (candidate % divisor) > 0:
- divisor +=1
- if candidate == divisor:
- print candidate
- numPrimes+=1
- candidate+=1
- # this rearrangement makes it easier to optimise
- numPrimes= 1
- candidate = 3
- while numPrimes <= 1000:
- divisor = 2
- isPrime = True
- while divisor < candidate:
- if candidate % divisor == 0:
- isPrime = False
- divisor += 1
- if isPrime:
- print candidate
- numPrimes+=1
- candidate+=1
- # we know that for every divisor above the square root of anumber,
- # that number will have another divisor below the square root
- # so we check the smaller search space (below the square root).
- # we need to check the square root as well
- # just in case that number is the square of another prime
- from math import sqrt
- numPrimes= 1
- candidate = 3
- while numPrimes <= 1000:
- divisor = 2
- isPrime = True
- while divisor <= sqrt(candidate):
- if candidate % divisor == 0:
- isPrime = False
- divisor += 1
- if isPrime:
- print candidate
- numPrimes+=1
- candidate+=1
- # if a number is divisible by 4, it's also divisible by 2.
- # the same property holds for all non-prime numbers
- # so you only need to check divisibility by prime numbers
- # this change provides support for storing and checking all primes
- # again, only primes below the sqrt!
- from math import sqrt
- primes = [2]
- candidate = 3
- while len(primes) <= 1000:
- isPrime = True
- for prime in primes:
- if candidate % prime == 0:
- isPrime = False
- if prime > sqrt(candidate):
- break
- if isPrime:
- print candidate
- primes.append(candidate)
- candidate+=1
- # 2 is the only even prime number, so we don't need to check even numbers
- # we're also evaluating the sqrt of a number multiple times in a loop
- # it never changes, so we can store that in a variable to save extra processing
- from math import sqrt
- primes = [2]
- candidate = 3
- while len(primes) <= 1000:
- isPrime = True
- sqrtCandidate = sqrt(candidate)
- for prime in primes:
- if candidate % prime == 0:
- isPrime = False
- if prime > sqrtCandidate:
- break
- if isPrime:
- print candidate
- primes.append(candidate)
- candidate+=2 #candidate can't be even for this to work
- # these small optimisations can only go so far without changing
- # the method we use to calculate primes altogether
- # The above method is called Trial Division.
- # It's probably the worst prime calculating method that is actually used.
- # If you care about fast computation of LOTS of primes,
- # have a look at the Sieve of Eratosthenes
- # It's a good place to start.
Advertisement
Add Comment
Please, Sign In to add comment