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
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 ...
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
77 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
378 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
113 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
202 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
165 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 ...
5
votes
1answer
833 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
718 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
246 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
195 views

Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000. ...
5
votes
2answers
129 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
144 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
6k 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: ...
4
votes
3answers
874 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
795 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
96 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
419 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
347 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
736 views

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

How can I optimize this? ...
3
votes
1answer
69 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
600 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
106 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
919 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
201 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
180 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
234 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 "...
28
votes
4answers
2k 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
979 views

Eratosthenes Sieve optimized in C

I wrote yet another optimized single-threaded Eratosthenes Sieve implementation in C: erato.c ...
4
votes
1answer
209 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
574 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
967 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 ...
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
330 views

Sieve of Eratosthenes using a Javascript array

Any feedback on my code would be greatly appreciated. ...
2
votes
1answer
141 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
199 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
374 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
285 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
927 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
votes
2answers
377 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,...
5
votes
1answer
62 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
404 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
212 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
125 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
508 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: ...