The Sieve of Atkin is probably what you’re looking for, its upper bound running time is O(N/log log N). If you only run the numbers 1 more and 1 less than the multiples of 6, it could be even faster, as all prime numbers above 3 are 1 away from some multiple of six. Resource … Read more
I recommend using 92821. Here’s why. To give a meaningful answer to this you have to know something about the possible values of i and j. The only thing I can think of in general is, that in many cases small values will be more common than large values. (The odds of 15 appearing as … Read more
a slightly different approach: use a bitarray to represent the odd numbers 3,5,7,… saving some space compared to a list of booleans. this may save some space only and not help speedup… from bitarray import bitarray def index_to_number(i): return 2*i+3 def number_to_index(n): return (n-3)//2 LIMIT_NUMBER = 50 LIMIT_INDEX = number_to_index(LIMIT_NUMBER)+1 odd_primes = bitarray(LIMIT_INDEX) # index … Read more
Edited: My answer to the question is: Yes, you can definitely use the Task Parallel Library (TPL) to find the primes to one billion faster. The given code(s) in the question is slow because it isn’t efficiently using memory or multiprocessing, and final output also isn’t efficient. So other than just multiprocessing, there are a … Read more
The Sieve of Atkin pseudo code from the Wikipedia article you’ve quoted contains the answers to your questions or the discussion about the article for which Will Ness has provided a link does, although you may not be able to put the information together. Short answers are as follows: The three equations come from Atkin’s … Read more
using a regexp 🙂 #!/usr/bin/python import re, sys def isPrime(n): # see http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ return re.match(r’^1?$|^(11+?)\1+$’, ‘1’ * n) == None N = int(sys.argv[1]) # number of primes wanted (from command-line) M = 100 # upper-bound of search space l = list() # result list while len(l) < N: l += filter(isPrime, range(M – 100, M)) … Read more
Three ways: 1. int main () { for (int i=2; i<100; i++) for (int j=2; j*j<=i; j++) { if (i % j == 0) break; else if (j+1 > sqrt(i)) { cout << i << ” “; } } return 0; } 2. int main () { for (int i=2; i<100; i++) { bool prime=true; … Read more
The only deterministic, polynomial-time algorithm for primality testing I know of is the AKS primality test (http://en.wikipedia.org/wiki/AKS_primality_test). However, there are a lot of very good randomized primality tests that are fast and have extremely good probability of success. They usually work by finding whether the number is composite with exponentially good probability, so they’ll either … Read more
Normally, definition of primes stream in Richard Bird’s formulation of the sieve of Eratosthenes is self-referential: import Data.List.Ordered (minus, union, unionAll) ps = 2 : minus [3..] — `:` is “cons” (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r) [] ps) The primes ps produced by this definition are used as the input … Read more
bool isPrime(int number){ if(number < 2) return false; if(number == 2) return true; if(number % 2 == 0) return false; for(int i=3; (i*i)<=number; i+=2){ if(number % i == 0 ) return false; } return true; }