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
1answer
64 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
413 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 ...
18
votes
1answer
1k 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 ...
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 ...
3
votes
1answer
241 views

Sieve32, a simple 32 bit sieve returning IEnumerable<uint> using C#

What a difference 1 bit makes! This very fast, simple sieve of Eratosthenes quickly finds 32 bit primes. It uses a memory efficient BitArray for odd numbers – but ...
4
votes
2answers
131 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 ...
1
vote
1answer
513 views

Sieve of Eratosthenes to print prime numbers in a given range

This is my implementation for Sieve of Eratosthenes in Java.Please let me know how can I further improve my code: ...
14
votes
3answers
697 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...
15
votes
3answers
986 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): ...
1
vote
1answer
287 views

Sum of primes between two number from optimized Sieve of Eratosthenes

Here is the code that I wrote to give me sum of prime numbers between n and m: ...
3
votes
1answer
775 views

Sieve of Eratosthenes Optimization in Rust

When I want to try a new language, I first try to write a fairly basic sieve of Eratosthenes project in said language. This is a very simple algorithm, with predictable results, and can even be ...
0
votes
1answer
126 views

A non-static Sieve of Eratosthenes class, version 1

Over the years I’ve seen many C# sieves and despite their varying internals all that I have seen invariably are a static method that returns a List<int>, ...
3
votes
2answers
204 views

Effecient Use Sieve of Eratosthenes algorithm

Given this as a the Problem Statement Given two numbers, find the sum of prime numbers between them, both inclusive. Input: The first line contains the number of test cases T. Each ...
1
vote
0answers
135 views

R-Python sieve, 36 times slower than World Record

I decided to write a sieving prime-finding programme and make it fast. It works correctly but counting the primes below 10**9 takes 36 times as primesieve ...
4
votes
1answer
522 views

Finding number of primes till n - Sieve of Eratosthenes

I've written a ruby implementation for Sieve of Eratosthenes algorithm, however benchmarking it against the Ruby's Prime module I have still a far slower algorithm -...
5
votes
2answers
182 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? ...
3
votes
1answer
513 views

Optimization of a basic Sieve of Eratosthenes algorithm

I have the following Sieve of Eratosthenes algorithm: ...
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 ...
3
votes
1answer
103 views

Factors sieve optimization

I've written a more powerful version of the Sieve of Eratosthenes, this Sieve returns the number of factors of all the numbers below the limit.Sadly the running ...
5
votes
2answers
475 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
1answer
420 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 ...
3
votes
3answers
179 views
2
votes
2answers
462 views

Sieve of Eratosthenes JavaScript implementation - performance very slow over a certain number

I've been playing around with the code challenges on projecteuler.net. A few of them involve prime numbers, so I've created a function to find them based on the sieve of Eratosthenes. It works fine, ...
7
votes
1answer
558 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,...
5
votes
3answers
952 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 ...
2
votes
1answer
3k views

A prime number sieve using recursion

Out of curiosity, I built a recursive Sieve of Eratosthenes in Python and I was wondering how it could be improved for efficiency and how it can improved to be aligned with python best practices. ...
5
votes
1answer
310 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, ...
6
votes
1answer
514 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 ...
2
votes
2answers
320 views

Attemped Sieve of Eratosthenes

I've just done Project Euler question 10: Find the sum of all the primes below two million. I get the correct answer and it takes about 3.5-4 seconds to run. I tried to use the Sieve of ...
1
vote
1answer
467 views

Sieve of Eratosthenes in Haskell

I've implemented the Sieve of Eratosthenes algorithm in Haskell. Please take a look. Any suggestions are greatly appreciated :) ...
3
votes
2answers
170 views

Efficiency of sieve of Eratosthenes

Can I make this more efficient? ...
5
votes
5answers
5k views

Creating vector of primes using Sieve of Eratosthenes

Please review my Sieve of Eratosthenes implementation. ...
5
votes
3answers
795 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: ...
11
votes
2answers
906 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.) ...
1
vote
2answers
211 views

Sieve of Erathosthenes speedup

While reading HackerNews, I learned about a data set of the first 50 million primes. This would be a lot, but his website has disclaimer: n this directory I have the first fifty million primes in ...
3
votes
2answers
201 views

Optimizing Sieve of Eratosthenes for larger numbers

I am having difficulty optimizing my code for the Sieve of Eratosthenes. The code works fine for smaller numbers (up to 10,000) but takes a long time to run for numbers over 100,000. ...
6
votes
2answers
327 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\$...
1
vote
1answer
199 views

Writing a Pythonic prime sieve

I'm practicing writing code less by brute force. I'd like feedback for writing a prime sieve more Pythonic, simpler, or more creatively perhaps. ...
8
votes
7answers
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> ...
8
votes
2answers
969 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 ...
7
votes
3answers
390 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 ...
16
votes
2answers
3k 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 ...
11
votes
4answers
399 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 ...
6
votes
4answers
1k views

Threshing: Sieve of Eratosthenes

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly. I made this super simple, trying to learn a little bit about ...
5
votes
2answers
814 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 ...
7
votes
5answers
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 ...
11
votes
5answers
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, ...
5
votes
3answers
767 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
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
2answers
263 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 ...