# 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.

162 questions
Filter by
Sorted by
Tagged with
237 views

### Extending Sieve of Eratosthenes beyond a billion - follow-up

Follow up form Extending Sieve of Eratosthenes beyond a billion Taking suggestions from the comments on the previous post: Updated Code: This takes about 22 seconds for MAX as $10^9$ to reach "...
5k views

### Implementation of Sieve of Eratosthenes in Python

The following is my implementation of Sieve of Eratosthenes. Can somebody please review it? Am I adhering to the algorithm and is it a reasonable implementation of it? ...
380 views

### Java Implementation of Sieve of Eratosthenes algorithm

I previously asked about my implementation of the Sieve of Eratosthenes algorithm here. After looking at all of the feedback, I have reworked the code to make it significantly more efficient. However,...
308 views

### Quadratic Primes - Project Euler 27

Project Euler Problem 27 Euler discovered the remarkable quadratic formula: $n^2 + n + 41$ It turns out that the formula will produce $40$ primes for the consecutive values $n = 0$...
1k views

### Generating primes with Sieve of Eratosthenes

There are many problems on the Internet that require you to find prime numbers, so I decided to write a set of functions to find them. I used the Sieve of Eratosthenes for generating the primes as it ...
365 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 ...
1k views

### Goldbach's Conjecture using Sieve of Eratosthenes

I created a simple Java program to calculate Goldbach's conjecture and I was wondering how I could improve it (besides using clearer prompt messages). ...
87 views

### Object oriented, runtime expandable Sieve of Eratosthenes

In answering this question, it seemed to me that it would be nice to have a runtime expandable Sieve of Eratosthenes. This is my implementation of that notion. Design I've created a class named <...
206 views

I've implemented the prime sieve of Eratosthenes in Haskell using a mutable array of unboxed Bools instead of the usual pure and immutable datastructures. My main concern with this code is speed. For ...
151 views

### C the sum of primes

The challenge is to calculate the sum of the first 1000 primes. The code applies a sieve thanks to past answer, here, and works but I wonder about the flexibility of this solution. ...
295 views

### Sieve of Eratosthenes for prime generation

I was originally going to write this intro as just being the bare-bones "here's my problem, here are some ideas, what do you recommend" format (which I am still going to follow, mind you), but I've ...
357 views

### Purely functional Sieve of Eratosthenes

Many implementations of Sieve of Eratosthenes (used to find prime numbers up to a given n) use a temporary mutable array to keep track of which numbers are composites. I'm looking to write a purely ...
489 views

### Project Euler #10 in Swift - Summation of primes

I just finished Project Euler #10 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. I hope I learned some from ...
127 views

### Python3 - Prime Sieve

I've implemented two prime sieves in python 3 to find all prime numbers up to an upper limit n - n exlusive. The first one is ...
108 views

### Understanding RSA key generation and implementation in Java

Here is an attempt to leverage Java's BigInteger class to implement the RSA algorithm, as well as md5 and sha512 hashing functions to generate keys for what I hope to be strong cryptography. My prayer ...
399 views

### Sieve32FastV2 - A fast parallel Sieve of Eratosthenes

I’ve created a much cleaner, better designed version to my parallel sieve. I’ve implemented most of EBrown’s micro-optimizations but also revamped the code on my own (that is not in direct response ...
1k views

### Eratosthenes Sieve optimized in C

I wrote yet another optimized single-threaded Eratosthenes Sieve implementation in C: erato.c ...
4k views

### Creating vector of primes using Sieve of Eratosthenes

Please review my Sieve of Eratosthenes implementation. ...
197 views

### Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000. ...
631 views

### Improved RandomGenerator with nextPrime() method

I am trying to implement a method that generates a random prime number between a given range. I have tried using a simple method to find whether a number is prime or not, advanced simple method, ...
2k views

### Find the nth prime number

It's a long time since I've written a Sieve of Eratosthenes (about 3 decades, I think, in ZX Basic). So I decided to revisit in the light of experience. Rather than allocating a vector of unknown ...
465 views

### Optimization of a “Sieve of Eratosthenes” in Java

I have created a simple Pseudo "Sieve of Eratosthenes," for a class in Java. I am looking for the most optimized option, or at least an option that is more optimized than current. If there is any ...
765 views

### Prime less than N that is a sum of the most consecutive other primes

Here's a Python implementation of the Sieve of Eratosthenes: ...
855 views

### Project Euler Problem #10

I've read other solutions about solving the 10th problem for Project Euler (finding the sum of all prime numbers under 2,000,000) but I wanted to try it on my own using the Sieve of Eratosthenes ...
2k views

### Sieve of Eratosthenes - Standard and Optimized implementation

I am a Java developer who is taking Python for the first time. I'm sure this is not at all elegant since I am thinking more in C syntax. ...
403 views

### Prime number calculator using Sieve of Eratosthenes

I've been writing this prime number calculator, and I've gotten it pretty quick in comparison to most I've seen knocking about. This one uses the Sieve of Eratosthenes approach, and I've optimised the ...
858 views

### Find the 10001st prime number (in C++)

I wrote this solution for project Euler #7, to find the 10001th prime number using sieve of eratosthenes. It's really slow though. Any suggestions to improve performance (without using more complex ...
134 views

### Sieve of Eratosthenes with a Swing UI

I'm fairly new to Java. I want to divide my code into 3 classes. First class to contain my GUI, second to compute the algorithm and third class to write results in my file. I have the code working but ...
804 views

### Submitting a Java program which implements the Sieve of Eratosthenes

I would like some feedback on a Java program which implements the Sieve of Eratosthenes to find prime numbers. Some of the 'features' I've included in the program include: It uses a ...
245 views

### Reduce Prime Sieve Memory Consumption 2

I've made a prime number generator (for Project Euler). It uses Euler's Sieve (a modified Sieve of Eratosthenes), with a mod 30 step. I'd like to reduce the memory consumption to 4/15 what it ...
62 views

### Prime Sieve and brute force #2

Based on my previous attempt. Prime Sieve and brute force Trying to make the interface simpler I have moved all the code into a class. This way I can keep track of the ...
256 views

### Sieve of Eratosthenes prime number finder up to n in C++

I'be been learning c++ recently and as an exercise I wanted to write a program to find numbers up to n using sieve of Eratosthenes. I'm new to c++ and programming in general so I'm not sure if this ...
502 views

### Prime Sieve in Rust (Sieve of Eratosthenes)

I am learning Rust and I decided to make a prime sieve program. It works and has comparable performance to my equivalent C program. I am new to Rust so I would like some feedback on my code. In ...
1k views

### Segmented Sieve of Eratosthenes

I implemented this for the Prime Generator problem on SPOJ, but I am only getting 0.01s run-time, and would like to be able to match the run-times of the top submissions, which are all 0.00s. What ...
63 views

### Pythonic sieve of Erasthotones that saves results to file

I'd like to have some feedback on this sieve of erasthotones that I've wrote. It outputs all prime numbers up to n correctly (I've tested with the first 10k prime ...
686 views

### Psycho and ordinary numbers

The problem statement can be found here. In short, here's what the problem is about: You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number ...
3k views

### Sieve of Eratosthenes in Python 3

Currently, the code will generate a range of natural numbers from 1 to N and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as 0 and storing each ...
407 views

### Implementation of Sieve of Eratosthenes algorithm

I have made an implementation of Sieve of Eratosthenes algorithm in Java, and am not certain that it is as efficient as possible. I have looked at other peoples implementations on Google, and on this ...
179 views

### Bitmap-based Sieve of Erastothenes

I have written a simple implementation of Sieve of Erasthotenes (in C, MSVC flavour), which I believe is correct (source below). Is there a way to make it faster and more readable? ...
293 views

### Sieve of Eratosthenes in Scheme (R7RS)

I've seen many implementations of Sieve of Eratosthenes in Scheme, but I thought I'd try to write one that is both space- and time-efficient: Space-efficient: I use R7RS bytevectors as a bitset, ...
96 views

### Multiple rusty Sieves of Eratosthenes

To get more familiar with the multi-threading aspects in the Rust language I decided to multi-thread my earlier implementation of The rusty Sieve of Eratosthenes. I have to say that it is probably in ...
1k views

### Primes Without 1's

Requirement primes numbers which do not have digit 1 in it. Input The first line contains T, the number of test cases. Followed by T lines each contain two numbers M and N Output ...
391 views

### Sieve of eratosthenes with std::vector<bool>

How can I improve and optimise this code? ...
118 views

### Incremental Sieve of Eratosthenes using iterators

I am in the process of learning Rust and am still having some issues with borrowing and ownership. I find myself trying to borrow mutable references that are already borrowed as immutable references ...
125 views

### Object-oriented approach to sieve of Eratosthenes

I was trying to implement the sieve of Eratosthenes entirely by myself, using only what I have learned so far. Now I'm wondering what I can do to improve my code's readability. Optimizing the ...
1k views

### Sieve of Eratosthenes in C#

Just because I've never written a real Sieve of Eratosthenes, I decided I should probably write one just to make sure I know what it is. I'd like (constructive) criticism on best practices, potential ...
146 views

### Sieve of Eratosthenes in Python

This is yet another take in Python for the infamous Sieve of Eratosthenes. I am a beginner in Python so any criticism is highly appreciated. ...
165 views

### Sieving for prime numbers

I wanted to implement the Sieve of Erathosthenes up to int.MaxValue in C#. No object is allowed to exceed 2Gb so you can't allocate a ...
I am tasked with being able to find the $n$th prime number. I've tried to implement something like the sieve of Eratosthenes in increments of 200. The code works and returns the $n$th prime number....