I'm playing through project Euler in my spare time, and it's come to the point where I need to do some refactoring. I've implemented Miller-Rabin, as well as a few sieves. I've heard before that si...

I read up on the sieve of Eratosthenes while solving a question on Project Euler. I'm sure you guys know which question im talking about. So here's the thing. My code manages to show all the primes...

We know that all primes above 3 can be generated using: 6 * k + 1 6 * k - 1 However we all numbers generated from the above formulas are not prime. For Example: 6 * 6 - 1 = 35 which is clearly...

Sieve of Eratosthenes memory constraint issue Im currently trying to implement a version of the sieve of eratosthenes for a Kattis problem, however, I am running into some memory constraints that m...

So, we can count divisors of each number from 1 to N in O(NlogN) algorithm with sieve: int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { cnt[j]++; ///...

I'm about to implement the Sieve of Eratosthenes and have a general question regarding the sieve-array. I've implemented the sieve quite a few times now (in C) and always used an array of uint8_t...

The program below [Python 3.4] is a simple Eratosthenes sieve: from itertools import * def excl(ns,pr): return (i for i in ns if i%pr) def sieve(ns): while True: pr=next(ns) yield pr ns=excl(...

I have implemented the Sieve of Atkin and it works great up to primes nearing 100,000,000 or so. Beyond that, it breaks down because of memory problems. In the algorithm, I want to replace the mem...

J will answer the n-th prime via p:n. If I ask for the 100 millionth prime I get an almost instant answer. I cannot imagine J is sieving for that prime that quickly, but neither looking it up in a...

I recently became very interested in prime numbers and tried making programs to calculate them. I was able to make a sieve of Sundaram program that was able to calculate a million prime numbers in ...

What's the specific problem with my foldl that prevents it from terminating or producing output? First I achieved a sieve for primes. It's not the best, but it works just fine as (for example) tak...

I am trying to write a function that calculates all odd prime numbers from 1..n using the "Sieve of Sundaram" algorithm. Here is my try: sSund :: Integer -> [Integer] sSund n = [ i * 2 + 1 | i...

I need to do the reverse of finding the Nth prime, i.e. Given a prime number, I need to find its position in 2, 3, 5, 7... The prime number can be large, in the order of 10^7. Also, there are a ...

When following the procedure on wikipedia for wheel factorization, I seem to have stumbled into a problem where the prime number 331 is treated as a composite number if I try to build a 2-3-5-7 whe...

What exactly do they do? I know one possible use of @ (assigning a name at the start of a pattern match), but haven't been able to find anything on ~. I found them in the following code snippet, t...