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.
186
questions
4
votes
1
answer
117
views
Sieve of Eratosthenes solution for CodeEval
The code below takes integer n as input, and delivers a list of all primes up to integer n using the Sieve of Eratosthenes.
My question is, could you please help me optimize this code? Is it ...
- 143
7
votes
3
answers
965
views
Sieve Of Erastothenes using Java
have started learning Java recently and was looking into some easy algorithms.
I found the Sieve Of Erastothenes algorithm here
I am trying to get better at writing good code for my solutions. Please ...
4
votes
1
answer
255
views
Segmented Sieve of Eratosthenes in Scala
I'm trying to solve PRIME1 in SPOJ with the following Scala snippet:
Peter wants to generate some prime numbers for his cryptosystem. Help
him! Your task is to generate all prime numbers between ...
- 141
4
votes
2
answers
259
views
Sieve of Eratosthenes in Erlang
I just started learning Erlang. Here is my crack at the Seive, based on (https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf):
...
- 139
6
votes
2
answers
307
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 "...
- 823
32
votes
4
answers
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 ...
- 823
5
votes
3
answers
1k
views
Eratosthenes Sieve optimized in C
I wrote yet another optimized single-threaded Eratosthenes Sieve implementation in C:
erato.c
...
- 329
4
votes
1
answer
263
views
Windowed Sieve of Eratosthenes in Java
I wanted to try and use the Sieve of Eratosthenes to find all prime numbers between some arbitrary bounds 1 <= m <= n. The simple implementation of the sieve ...
- 823
10
votes
3
answers
693
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!
...
- 101
7
votes
5
answers
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 ...
- 223
6
votes
2
answers
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).
...
- 171
3
votes
1
answer
391
views
Sieve of Eratosthenes using a Javascript array
Any feedback on my code would be greatly appreciated.
...
2
votes
1
answer
156
views
Yet another Sieve of Eratosthenes in Java
I wanted a reusable class for generating a list of primes till some arbitrary (but reasonable) limit. So, I wrote a class Primes that implements the Sieve of ...
- 3,017
4
votes
1
answer
391
views
Sieve of Eratosthenes Primes Efficiency
I'm fairly new to Java and was trying to make a program that's generates the primes from 2 - 100. I originally had a design of my own making but it was fairly inefficient so I did some research and ...
- 143
10
votes
0
answers
721
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 ...
- 6,277
6
votes
1
answer
4k
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 ...
- 829
6
votes
1
answer
353
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 ...
- 829
10
votes
1
answer
2k
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 ...
- 6,277
6
votes
2
answers
483
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,...
- 507
6
votes
1
answer
77
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 ...
- 635
5
votes
3
answers
448
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 ...
- 507
20
votes
1
answer
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 ...
- 66.4k
4
votes
7
answers
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
...
- 676
4
votes
1
answer
399
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 ...
- 6,277
4
votes
2
answers
159
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 ...
- 823
1
vote
1
answer
516
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:
...
17
votes
3
answers
961
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...
- 6,277
16
votes
3
answers
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):
...
- 1,026
1
vote
1
answer
295
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:
...
- 676
4
votes
1
answer
1k
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 ...
- 143
0
votes
1
answer
154
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>, ...
- 6,277
3
votes
2
answers
303
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 ...
- 676
1
vote
0
answers
154
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 ...
- 27.5k
4
votes
1
answer
570
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 -...
- 163
5
votes
2
answers
223
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?
...
- 151
3
votes
1
answer
648
views
Optimization of a basic Sieve of Eratosthenes algorithm
I have the following Sieve of Eratosthenes algorithm:
...
- 761
4
votes
3
answers
3k
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 ...
user34073
3
votes
1
answer
122
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 ...
- 27.5k
5
votes
2
answers
540
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 ...
- 135
5
votes
1
answer
577
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 ...
- 193
3
votes
3
answers
197
views
3
votes
2
answers
536
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, ...
- 131
7
votes
1
answer
607
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,...
- 103
5
votes
3
answers
1k
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 ...
- 51
2
votes
1
answer
5k
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.
...
- 177
5
votes
1
answer
442
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, ...
- 2,342
6
votes
1
answer
591
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 ...
- 413
2
votes
2
answers
347
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
1
answer
596
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 :)
...
- 401
3
votes
2
answers
182
views
