Stack Overflow
Stack Overflow

Questions tagged [sieve-of-atkin]

A modern prime number sieve with better computational complexity than that of the sieve of Eratosthenes.

A modern prime number sieve with better computational complexity than that of the sieve of Eratosthenes. See https://en.wikipedia.org/wiki/Sieve_of_Atkin.

25 questions
32
votes
1 answer

Sieve of Atkin - Explanation and Java example

I have read about Sieve of Atkin on Wikipedia but the wiki is limited at the moment. I was looking for an explanation of Sieve of Atkin at a high level and an example in Java. Thanks.
Jash Sayani
  • 1,241
  • 3
  • 12
  • 17
22
votes
5 answers

Sieve of Atkin explanation

I am doing a project at the moment and I need an efficient method for calculating prime numbers. I have used the sieve of Eratosthenes but, I have been searching around and have found that the sieve of Atkin is a more efficient method. I have found…
marc lincoln
  • 1,551
  • 4
  • 21
  • 25
21
votes
2 answers

The Sieve of Atkin

I have been trying to learn algorithms for generating prime numbers and I came across Sieve of Atkin on Wikipedia. I understand almost all parts of the algorithm, except a few. Here are the questions: How are the three quadratic equations below…
Shiv
  • 471
  • 4
  • 8
10
votes
4 answers

Prime number hard drive storage for very large primes - Sieve of Atkin

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 memory based array with a hard drive based array.…
WyomingGeezer
  • 157
  • 11
7
votes
6 answers

C#: Implementation of the Sieve of Atkin

I was wondering if someone here have a good implementation of the Sieve of Atkin that they would like to share. I am trying to implement it, but can't quite wrap my head around it. Here is what I have so far. public class Atkin :…
Svish
  • 152,914
  • 173
  • 462
  • 620
6
votes
2 answers

Segmented Sieve of Atkin, possible?

I am aware of the fact that the Sieve of Eratosthenes can be implemented so that it finds primes continuosly without an upper bound (the segmented sieve). My question is, could the Sieve of Atkin/Bernstein be implemented in the same way? Related…
K.Steff
  • 2,164
  • 3
  • 19
  • 25
5
votes
2 answers

Why does my naive implementation of the Sieve of Atkins exclude 5?

I wrote an extremely naive implementation of the Sieve of Atkin, based on Wikipedia's inefficient but clear pseudocode. I initially wrote the algorithm in MATLAB, and it omits 5 as a prime number. I also wrote the algorithm in Python with the same…
Ricardo Altamirano
  • 14,650
  • 21
  • 72
  • 105
3
votes
0 answers

Highly Factorized Sieve of Eratosthenes

Just for fun, I'm trying to implement the pseudocode from this StackOverflow answer for the highly factorized Sieve of Eratosthenes in C++. I can't figure out why my code returns both prime and non-prime numbers. Am I implementing these for loops…
tn3rt
  • 260
  • 3
  • 13
3
votes
1 answer

Why is my implementation of the Sieve of Atkin overlooking numbers close to the specified limit?

My implementation of Sieve of Atkin either overlooks primes near the limit or composites near the limit. while some limits work and others don't. I'm am completely confused as to what is wrong. def AtkinSieve (limit): results = [2,3,5] sieve =…
imperialdogma
  • 43
  • 1
  • 7
3
votes
1 answer

C++ Sieve of Atkin overlooks a few prime numbers

Recently I've been working on a C++ prime generator that uses the Sieve of Atkin ( http://en.wikipedia.org/wiki/Sieve_of_atkin ) to generate its primes. My objective is to be able to generate any 32-bit number. I'll use it mostly for project euler…
Axel Magnuson
  • 1,192
  • 1
  • 10
  • 26
3
votes
5 answers

C#: How to make Sieve of Atkin incremental

I don't know if this is possible or not, but I just gotta ask. My mathematical and algorithmic skills are kind of failing me here :P The thing is I now have this class that generates prime numbers up to a certain limit: public class Atkin :…
Svish
  • 152,914
  • 173
  • 462
  • 620
3
votes
2 answers

Sieve of Atkin malfunctioning for very high limits

I am attempting to solve Project Euler problem 10 where the user is asked to calculate the sum of all the primes less than two million. I've written the following by studying the pseudocode on Wikipedia but the answer it generates seems to be…
user360907
1
vote
0 answers

If the time complexity of Sieve of Atkins is better than Sieve of Eratosthenes, why does Eratosthenes always have a quicker runtime

I'm doing a project on Sieve of Atkins and I was exploring why this algorithm was created. From what I understood was that it was a way of finding prime numbers and it ran faster than Sieve of Eratosthenes. But from what I've read, Sieve of Atkins…
CrashMan123
  • 57
  • 6
1
vote
1 answer

Sieve of Atkin C++ Implementation does not tag some Primes

I implemented the Sieve of Atkin in C++ to return a Vector of type bool, but it does not tag some Primes. // Example program #include #include std::vector listPrimes(int limit){ std::vector primes(limit); …
Aswin Mohan
  • 952
  • 1
  • 11
  • 26
1
vote
1 answer

Python Implementation of the Sieve of Atkin

My code works to give most primes, however it still include 1 and misses some numbers: 23 and 47 (when calculating prime numbers under 100). For some reason it includes 91, any ideas why?? I have been using the Wikipedia instructions for the Sieve…
Tom
  • 918
  • 6
  • 19
1
2