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.
1
vote
0answers
23 views
Incremental Sieve of Eratosthenes
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
57 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
68 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
48 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
86 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
61 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
77 views
3
votes
2answers
102 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
70 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?
...
6
votes
2answers
88 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
134 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
80 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 ...
0
votes
1answer
442 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
129 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, ...
1
vote
2answers
237 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
285 views
8
votes
1answer
533 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
286 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 ...
3
votes
0answers
86 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
760 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
610 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
113 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
387 views
Eratosthenes' and Sundaram's prime sieves in Python
I recently started playing with Python. What can I do better?
...
3
votes
1answer
454 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
373 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
501 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
4k 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?
...
4
votes
5answers
124 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
236 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
53 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
693 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
80 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 <...
5
votes
1answer
223 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 ...
5
votes
1answer
339 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 ...
8
votes
1answer
428 views
Prime sieve for all primes up to a number
As a beginner to C++, I wanted to make something using what I was learning, so I did this to learn about arrays. This implements the Sieve of Eratosthenes to find the primes up to a limit.
I didn't ...
8
votes
1answer
230 views
Sieve of Eratosthenes performance; Scala very slow compared to Node.js
I am new to Scala so it might show. I am learning it for one of my classes and have to write a performance benchmark. I have written the Sieve of Eratosthenes in both Node.js and Scala, and my Node.js ...
5
votes
4answers
1k 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 ...
4
votes
2answers
845 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 ...
4
votes
2answers
887 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....
3
votes
2answers
76 views
Number Theory Inhibitor Calculator
I've been working on generating primes and prime products quickly to aid me in my research on prime numbers, their density, etc. The answer to my Large Number Limit Extravaganza question proved to be ...
1
vote
1answer
328 views
Finding numbers divisible by primes in a given range
The problem statement (Codeforces#
385C) is this:
We are given a sequence of \$n\$ numbers, i.e. \$x_i\$ and \$m\$ queries to find how many of these are divisble by primes between two given numbers ...
1
vote
1answer
99 views
Custom Sieve of Eratosthenes
I'm trying to improve my code to find all the prime numbers within a set range as fast as possible, and I am trying to make it even faster. On my github page here, I have some optimization settings ...
6
votes
2answers
197 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 ...
4
votes
2answers
159 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 ...
6
votes
4answers
1k views
Optimise Sieve of Eratosthenes
I have written the following code for finding out the prime numbers less than or equal to n. When I enter the input n = 10^7, my ...
4
votes
1answer
586 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 ...
2
votes
1answer
592 views
Unbounded Sieve of Eratosthenes in Swift
I've spent a while teaching myself Swift, and decided to take on the challenge of writing an unbounded Sieve of Eratosthenes to challenge myself. This is actually the first time I've written an ...
1
vote
3answers
191 views
Finds all the prime numbers up to n using a strange pattern
Here's an odd pattern I found for sieving out composite numbers to find primes. I wrote it myself, originally thinking I made an indexing error, but it turned out to work after removing squares.
<...
7
votes
2answers
228 views
Sieve of Eratosthenes and twin prime finder
I made this program to find primes and twin pairs. I'd like feedback on anything from formatting to content to technique. In short: how would this be different if it was written by an experienced ...
