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.
165
questions
1
vote
0answers
51 views
Zen and the Sieve of Eratosthenes - Part 1: A Basic Windowed Sieve
The Sieve of Eratosthenes is one of the oldest known algorithms and yet it is still the best method for sieving prime numbers in bulk in many situations. It is brutally simple, but to make it brutally ...
2
votes
1answer
46 views
Further Optimizing a Segmented Sieve of Eratosthenes
I've implemented a Segmented Sieve of Eratosthenes that assumes each segment is about length \$ \sqrt{N}\$ for some upper limit \$N\$.
I further optimized the function by skipping all the evens when ...
4
votes
4answers
773 views
Sum of primes under a certain number
I have tried two different methods to find the sum of primes under a certain number. However both of these methods end up taking a very long time for large numbers. How can I optimise either of these ...
4
votes
1answer
83 views
Prime Number Table, i.e. List<int>
I have written many variations of the Sieve of Eratosthenses, which is the fastest way to generate a large collection of primes. (@slepic asked for clarification, which I provide in an answer below. ...
5
votes
2answers
71 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 ...
7
votes
1answer
151 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 ...
11
votes
2answers
160 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 ...
8
votes
1answer
148 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 ...
1
vote
2answers
94 views
Optimizing the Sieve of Eratosthenes for prime generation
I've been on a Project Euler spree and I've been solving problems and as you might know, many of them require you to use prime numbers. I've been using the following code to generate and store primes ...
4
votes
1answer
79 views
Incremental Sieve of Eratosthenes Generator
So I was fiddling around with the Euler challenges. One of the things they mentioned in their discussions of the solutions is the Sieve of Eratosthenes and that you can only use it when you know an ...
3
votes
2answers
148 views
Sum of primes up to 2 million using the Sieve of Eratosthenes
I've solved question 10 on Project Euler using the Sieve of Eratosthenes, what can I do to optimize my code?
...
11
votes
3answers
2k views
Prime sieve in Python
I was trying to write Sieve for the first time and I came up with this code:
...
5
votes
1answer
64 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 ...
14
votes
3answers
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.
...
9
votes
3answers
250 views
3
votes
1answer
73 views
Efficiency of a recursive implementation of the Sieve of Erasthotenes in Python
I implemented the Sieve of Erasthotenes recursively using filter and I was wondering how efficient this implementation is and wether a non-recursive implementation ...
4
votes
2answers
127 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 ...
1
vote
0answers
56 views
Incremental Sieve of Eratosthenes using unstable generators [duplicate]
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 ...
2
votes
1answer
124 views
Simple Sieve of Eratosthenes in Python 3
So yet another Sieve of Eratosthenes in Python 3.
The function returns a list of all primes smaller but not equal max_n.
The motivation is, as a practice, a ...
0
votes
1answer
257 views
Fast Prime Sieve (Python Implementation)
A modified version of the prime sieve. I actually doubt it could be implemented any faster, but I might be wrong:
...
0
votes
1answer
57 views
Computing a prime table in Rust
My objective is computing a table of primes up to n, where n is a natural number passed as an argument to the prime_table function.
Here is src/lib.rs:
...
2
votes
1answer
166 views
Faster Sieve of Eratosthenes
This is an implementation of the Sieve of Eratosthenes :
It takes advantages of the fact that all primes from 5 and above can be written as 6X-1 or ...
2
votes
2answers
78 views
Project Euler #10 (sum of primes less than two million) in Clojure
I'm new to Clojure and using some Project Euler problems to familiarize myself with the language's capabilities. Problem #10 asks to find the sum of all primes less than two million.
I wanted to ...
0
votes
3answers
95 views
3
votes
2answers
218 views
Sieve of Eratosthenes in Rust
This is a relatively simple implementation of the Sieve of Eratosthenes in Rust. The main objective is to find the \$n\$th prime quickly when \$n\$ might grow to huge numbers.
...
0
votes
2answers
97 views
Prime number generation - SPOJ
This is a program to generate prime numbers for a given range. The sieve of Eratosthenes algorithm was implemented, but still the SPOJ says time limit exceeded. Where can some optimizations be made?
...
7
votes
2answers
128 views
Prime number segmented sieve
I tried to solve the SPOJ prime number problem below. The code produced correct results, but Time limit exceeded and also memory need around 970M which is not efficient(?)
How can I optimize this ...
4
votes
1answer
148 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.
...
1
vote
0answers
106 views
Get prime divisors of an Int32 using a wheel
I recently played around with prime factorization using a prime wheel. Much of the heavy lifting is done by the PrimeWheel class. I think the implementation is ...
2
votes
2answers
1k views
Find primes using Sieve of Eratosthenes with Python
I was Googling for a 'correct' or 'efficient' implementation of the Sieve of Eratosthenes. I found them all more complicated than what I came up with. I am by no means a Python expert, so I was ...
3
votes
1answer
219 views
Functional Sieve of Eratosthenes in Clojure
For some reason, this is the first time I've ever written an implementation of the Sieve of Eratosthenes. I basically just stared at the Wikipedia walkthrough of the algorithm until it made sense, ...
2
votes
2answers
528 views
Finding the size of the largest connected component in a graph
Given this question, which simply can be explained as follows:
Given the number of nodes and the number of edges in a graph, find the size of the largest connected component of the graph. If this ...
4
votes
4answers
412 views
8
votes
1answer
2k 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 ...
4
votes
2answers
305 views
Sieve of Eratosthenes for small limits
I coded a sieve of Eratosthenes, I think it's quite fast for small limits. Any suggestions how to improve it? Especially for small limits, say limits < 50,000,000. (Also coded a parallel sieve (in ...
4
votes
0answers
108 views
Kotlin sieve using sequences
While learning about functional programming the simple sieve example was brought up in Haskell. I wanted to try a Kotlin implementation using sequences.
Are there any other quick wins without ...
8
votes
1answer
1k 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.
...
5
votes
4answers
635 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, ...
6
votes
1answer
128 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 ...
17
votes
5answers
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 ...
7
votes
4answers
579 views
Eratosthenes' and Sundaram's prime sieves in Python
I recently started playing with Python. What can I do better?
...
3
votes
1answer
608 views
Sieve of Eratosthenes using Java 8 streams
I am learning streams and lambdas in Java 8.
I wanted to implement the classic Sieve of Eratosthenes using lambdas and streams. This is my implementation.
...
1
vote
1answer
566 views
Rust nth prime implementation
I have implemented an nth prime algorithm in Rust that uses value lookup for n < 6, trial division for n < 1000, and a sieve function for n > 999. How can it be better optimized?
...
2
votes
2answers
666 views
Space and time efficient Algorithm for generating prime numbers
I have developed an algorithm for generating prime numbers (which turns out to be an optimized version of the Sieve of Eratosthenes) by reducing the space by a factor of 64.
...
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
6answers
148 views
Eratosthenes Sieve Implementation
My friend and I were doing an Eratosthenes Sieve implementation, it works, but I think there is a mistake with "n" and with the first for condition ("i<=n"). I think that condition can cause a ...
5
votes
2answers
262 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 ...
1
vote
1answer
57 views
Basic Sieve of Erosthenes
This is a basic command line program that, given a number, returns a list of primes up to and including that number. Also handles a lack of command line arguments and non-number arguments.
I ran into ...
7
votes
5answers
760 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 ...
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 <...
