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
1
vote
1answer
58 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
788 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
88 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 <...
7
votes
1answer
481 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
1answer
689 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
505 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
277 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
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
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 are ...
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....
3
votes
2answers
78 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 ...
2
votes
1answer
471 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
147 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
211 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
171 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 ...
6
votes
2answers
1k 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
868 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
192 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
264 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 ...
5
votes
3answers
202 views

Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000. ...
5
votes
2answers
168 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 ...
6
votes
1answer
153 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. ...
1
vote
3answers
7k views

Shortest prime number generator we could come up with?

I worked with a friend on the following prime number generator. Our goal was to make it as short and as fast as possible. This is what we came up with: ...
5
votes
3answers
910 views

Find All the Primes Between two Numbers

I wrote a solution to the Coding Challenge SPOJ Prime in C++ using the Sieve of Eratosthenes. How much Ever I tried I could not get over the Time Limit on SPOJ which is 6s for Primes upto 1000000000. ...
10
votes
2answers
1k views

Naive parallel Sieve of Eratosthenes in Java

My naive version now is too slow. I think setting/accessing concurrent atomic bit is way slower compared to access/modify an array of boolean. Second, the parallel execution only happens on the ...
5
votes
0answers
100 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 ...
7
votes
1answer
492 views

The rusty Sieve of Eratosthenes

To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N. I have created the following code that both prints the prime ...
6
votes
1answer
398 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 ...
-1
votes
1answer
831 views

Prime sieve implementation (using trial division) in C++

How can I optimize this? ...
3
votes
1answer
75 views

Writing a Rustic segmented prime number sieve

I wrote a prime number sieve in Ruby last year as part of a coding challenge, but lately I wanted to port it to Rust. I finally got around to it, but it's still intensely Rubinic. Before I take the ...
9
votes
3answers
604 views

A reference source for primes up to 64K (for unit tests)

In order to code the tests for my number theory library (a collection of routines that proved handy for coding challenges) I needed a reference source for primes up to 2^16. I did not want to ...
4
votes
1answer
107 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 ...
6
votes
3answers
921 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
1answer
213 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 ...
4
votes
2answers
200 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): ...
6
votes
2answers
253 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 "...
30
votes
4answers
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 ...
5
votes
3answers
1k views

Eratosthenes Sieve optimized in C

I wrote yet another optimized single-threaded Eratosthenes Sieve implementation in C: erato.c ...
4
votes
1answer
218 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 ...
10
votes
3answers
606 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! ...
7
votes
5answers
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 ...
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). ...
3
votes
1answer
338 views

Sieve of Eratosthenes using a Javascript array

Any feedback on my code would be greatly appreciated. ...
2
votes
1answer
147 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 ...
4
votes
1answer
237 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 ...
6
votes
0answers
480 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
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 ...
6
votes
1answer
312 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 ...
9
votes
1answer
1k 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 ...