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.

Filter by
Sorted by
Tagged with
6
votes
2answers
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 "...
6
votes
2answers
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? ...
6
votes
2answers
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,...
6
votes
2answers
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\$...
6
votes
3answers
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 ...
6
votes
1answer
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 ...
6
votes
2answers
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). ...
6
votes
1answer
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 <...
6
votes
2answers
206 views

Imperative Sieve of Eratosthenes using destructive updates in Haskell

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 ...
6
votes
1answer
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. ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
0answers
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 ...
6
votes
0answers
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 ...
5
votes
3answers
1k views

Eratosthenes Sieve optimized in C

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

Creating vector of primes using Sieve of Eratosthenes

Please review my Sieve of Eratosthenes implementation. ...
5
votes
3answers
197 views

Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000. ...
5
votes
4answers
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, ...
5
votes
4answers
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 ...
5
votes
2answers
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 ...
5
votes
3answers
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: ...
5
votes
3answers
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 ...
5
votes
1answer
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. ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
2answers
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 ...
5
votes
2answers
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
5
votes
3answers
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 ...
5
votes
1answer
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 ...
5
votes
3answers
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 ...
5
votes
2answers
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? ...
5
votes
1answer
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, ...
5
votes
0answers
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 ...
4
votes
7answers
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 ...
4
votes
4answers
391 views

Sieve of eratosthenes with std::vector<bool>

How can I improve and optimise this code? ...
4
votes
2answers
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 ...
4
votes
2answers
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 ...
4
votes
3answers
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 ...
4
votes
1answer
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. ...
4
votes
2answers
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 ...
4
votes
2answers
3k views

Sieve of Eratosthenes in JavaScript

I found this method kinda tough to get for a beginner like me, but I tried to do my best, and here's what I came up with. Is this good code regarding performance? Is there anything wrong with it? <...
4
votes
2answers
1k views

Get nth prime number using sieve of Eratosthenes

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