# Questions tagged [sieve-of-eratosthenes]

The Sieve of Eratosthenes is a prime-finding algorithm developed by the ancient Greek mathematician Eratosthenes. It works by writing down as many numbers as needed and then, traversing from lowest to highest, cross out all multiples of a number, beginning with 2. The numbers that remain are considered prime and the lowest of it will be used for the next run.

176 questions
Filter by
Sorted by
Tagged with
6k views

### Parallel sieve of Eratosthenes

For the first time, I tried to use threads by myself in order to implement a parallel sieve of Eratosthenes. The trick is that each time a prime is found, a thread is spawned to eliminate all the ...
3k views

### Extending Sieve of Eratosthenes beyond a billion

For MAX value of 1000000000 ($10^9$), it takes about 45 seconds to reach the line where it prints "done". How can I speed this ...
7k views

### Sieve of Eratosthenes - Python

I've been doing a lot of Project Euler lately and just wanted to make sure my implementation was as good as it could be. Does anyone have any suggestions to speed this up? ...
5k views

### Why is my Sieve of Eratosthenes using generators so slow

This is my prime sieve based on the Sieve of Eratosthenes. ...
2k views

### Compile-time sieve of Eratosthenes

There are many instances of prime number sieve implementation both here and other places on the web, but I wanted something a little different. In particular, I wanted to create a static array of the ...
3k views

### Sieve of Eratosthenes in C

I have attempted to implement the Sieve of Eratosthenes in C. It works rather quickly with values tested up to ten million: time ./soe.out 10000000 returns ...
848 views

### Sieve31, my sieve of Eratosthenes returning IEnumerable<int>

This very fast, simple sieve quickly finds 31 bit primes. It uses a memory efficient BitArray for odd numbers. How a 32 bit int...
2k views

### Eratosthenes sieve and MPI

I wrote this sieve of Eratosthenes with MPI, but I'm not sure if it's good enough. Should I use MPI_Scatter and MPI_Gather ...
4k views

### Generating prime numbers using Sieve of Eratosthenes with CUDA

I'm learning CUDA and wrote a little program which generates prime numbers using the Sieve of Eratosthenes. (I know the limitations of CUDA, specially with memory sizes and limits, but this program is ...
1k views

### Wheel based unbounded sieve of Eratosthenes in Python

Answering this SO question recently, I've developed the following code (based on a well-known Active Code recipe, as discussed here): ...
1k views

### Prime Sieve and brute force

Got caught up with this morning's C++ question. So I thought I would have a go. SO here is my attempt at printing the first 1001 primes. ...
9k views

### Sieve of Eratosthenes in C++

I'm looking for some feedback on my implementation of the algorithm. How can I improve it? I ran into problems when calculating the larger prime numbers > 46349 due to integer overflow, but fixed that ...
2k views

### Prime sieve in Python

I was trying to write Sieve for the first time and I came up with this code: ...
274 views

### Sieve of Eratosthenes in Vyxal

I'm trying to learn the golfing language Vyxal because I occasionally contribute to it, and I'm slightly ashamed I can't even use it. To do this, I started with implementing the Sieve of Eratosthenes ...
9k views

### Sieve of Eratosthenes

For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation. I would like to hear some suggestions for improvements, especially how to make it more efficient ...
2k views

### Parallel sieve of Eratosthenes, version 2

This question is a revision of Parallel sieve of Eratosthenes. The goal is to implement a sieve of Eratosthenes with parallel strikes out from the boolean array. I tried to fix the data races and all ...
405 views

### Threshed and Malachi'd: Sieve of Eratosthenes

I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes. This may be bordering on code-golfing, but I think that I have a pretty good piece of code here. Is ...
3k views

### Prime Number Sieving Algorithm

Last semester in my Masters Program I developed this code for sieving. My professor wants me to write a report that he might use locally within the school, but I feel like I've done nothing that new, ...
999 views

### Sieve of Eratosthenes - segmented to increase speed and range

A lot of the sieve code floating around here and on the 'net is sloppy or broken; in fact, I've yet to see a single one that is correct, clean (in the sense of avoiding superfluous iterations etc.) ...
635 views

### Segmented wheel Sieve of Eratosthenes in Python

Here is a new version of a segmented and wheel factorized Sieve of Eratosthenes. It currently uses mod 30 wheel factorization to eliminate multiples of 2, 3, and 5 in the sieve data structure to gain ...
1k views

### Sieve of Eratosthenes optimization

I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code? ...
1k views

### Sieve of Eratosthenes in C++11

Please point out every problem you see with this code. Any fundamental flaws, naming conventions, design decisions, you name it. ...
664 views

### Optimization on Sieve of Eratosthenes using vector<bool>

I am solving this prime generator problem from SPOJ: Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers! ...
1k views

### Naive parallel Sieve of Eratosthenes in Java

My naive version now is too slow. I think setting/accessing concurrent atomic bit is way slower compared to access/modify an array of boolean. Second, the parallel execution only happens on the ...
924 views

### Implementing Sieve of Eratosthenes faster

I wrote a version of sieve of eratosthenes: ...
4k views

### Sieve of Eratosthenes in Java

Here you can find my implementation of sieve of Eratosthenes in Java. ...
617 views

### A reference source for primes up to 64K (for unit tests)

In order to code the tests for my number theory library (a collection of routines that proved handy for coding challenges) I needed a reference source for primes up to 2^16. I did not want to ...
1k views

### Sieve32Fast - A very fast, memory efficient, multi-threaded Sieve of Eratosthenes

An improved version Sieve32FastV2 is available. The classical solutions for the Sieve of Eratosthenes fall into 2 camps: one uses a bool[], which is fast but very ...
998 views

### Sieve of Eratosthenes implementation is running slowly

I have written this code to find prime numbers, and it works well, but the calculation speeds are incredibly slow. Am I doing this wrong? I know that I might be really doing this the wrong way, but ...
13k views

### Find prime numbers under N

I'm using the Sieve of Eratosthenes to find primes numbers under N. Is there any performance problems you see with my approach? I used the LinkedList<Integer> ...
561 views

### Prime sieve for all primes up to a number

As a beginner to C++, I wanted to make something using what I was learning, so I did this to learn about arrays. This implements the Sieve of Eratosthenes to find the primes up to a limit. I didn't ...
9k views

### Sieve of Eratosthenes optimization

I have applied some optimizations like storing only odd values and starting to mark off from square of the number. Can it be optimized further? ...
4k views

### Sieve of Eratosthenes in C# with LINQ

Can someone look over this Sieve of Eratosthenes implementation? It seems almost too easy. Rather than maintaining a seperate bit[] to track prime/not prime, I'm ...
4k views

### Prime Number Generator in Swift

I would like to make (or improve my function) a function that returns an array of integers containing all the prime numbers from 2...n that can execute as quickly ...
2k views

### Finding nth Prime using Python and Sieve of Eratosthenes

I'm currently working through the Project Euler Problems using HackerRank to evaluate the code and I'm stuck on the 7th Problem. ...
285 views

...
311 views

### Sieve of Eratosthenes performance; Scala very slow compared to Node.js

I am new to Scala so it might show. I am learning it for one of my classes and have to write a performance benchmark. I have written the Sieve of Eratosthenes in both Node.js and Scala, and my Node.js ...
299 views

### Segmented and wheel factorized prime generator in Python

I recently discovered that it is much faster to generate primes using a Sieve of Eratosthenes (SoE) with a boolean array data structure than with a heap. Since then I have been looking for fast and ...
680 views

### The rusty Sieve of Eratosthenes

To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N. I have created the following code that both prints the prime ...
2k views

### A fast approach to prime number sieving (non-threaded array)

I am posting this question for input on comparisons between other sieving methods and opinions on what I have discovered. I believe this might be the fastest (singular, non-threaded) array ...
853 views

### "The Genuine Sieve of Eratosthenes" in C++14

The following C++ code implements the "Genuine Sieve of Eratosthenes" algorithm as described in Melissa O'Neill's classic paper. On my MacBook it computes the first 1,000,000 primes in about 11 ...
2k views

### Optimise Sieve of Eratosthenes

I have written the following code for finding out the prime numbers less than or equal to n. When I enter the input n = 10^7, my ...
424 views

### Modified Sieve of Eratosthenes has very long runtime

I am slowly moving through Project Euler, and have reached problem #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. I did a naive ...
1k views

### Project Euler #35 - Circular primes solution is slow

This is my code for project euler #35 (in Python): The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such ...
903 views

### Eratosthenes' and Sundaram's prime sieves in Python

I recently started playing with Python. What can I do better? ...
581 views

### Making prime (sieve) code faster and able to run on big numbers

For an input triple (a, b, c), the task is to count the number of integers in the inclusive range [a, b] which have c distinct prime factors. This entails factoring each of the numbers in the range [a,...
692 views

### Project Euler problem 50

I was just trying Project Euler problem 50. The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that ...
671 views

### Prime Number Generator Time Limit Exceeded

PRIME1- Prime Generator The code is working fine and it's generating a prime number from M to N but the only problem is I'm getting TLE when I submit my answer. How do I optimise my code to pass the ...