codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#Project Euler 7: #What is the 10,001st prime number? #Runtime, iteration setup: import time start = time.time() from math import log from math import sqrt bigO = 0 #Init nth = 10001 nmax = int(nth*(log(nth)+log(log(nth)))) nlist = list(range(3,nmax,2)) primes = [] #Sieve for primes (adapted from Euler's Sieve, Sieve of Eratosthenes): #1) Take the first prime of the list, then remove all elements that are multiples #2) Move to the next list element and repeat #3) Repeat for the first sqrt(nmax) primes # The remaining numbers should be prime since all shared factors have been removed #4) Append the remaining primes to the first set primes.append(2) while len(primes) <= int(sqrt(nmax))+1: p = nlist[0] primes.append(p) for n in nlist: if n%p == 0: nlist.remove(n) bigO += 1 primes.extend(nlist) #Output runtime = str((time.time()-start)*1000) print("Number of primes found: ",len(primes)) print("Prime(",nth,"): ",primes[nth-1]) print("#--- Run Stats ---#") print("Iterations: ",bigO) print("Total elapsed time: " + runtime + " milliseconds.")
Private
[
?
]
Run code
Submit