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
7
votes
5answers
2k views

A fast approach to prime number sieving (non-threaded array)

I am posting this question for input on comparisons between other sieving methods and opinions on what I have discovered. I believe this might be the fastest (singular, non-threaded) array ...
7
votes
3answers
386 views

Modified Sieve of Eratosthenes has very long runtime

I am slowly moving through Project Euler, and have reached problem #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. I did a naive ...
10
votes
4answers
1k views

Sieve of Eratosthenes optimization

I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code? ...
11
votes
4answers
399 views

Threshed and Malachi'd: Sieve of Eratosthenes

I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes. This may be bordering on code-golfing, but I think that I have a pretty good piece of code here. Is ...
6
votes
4answers
1k views

Threshing: Sieve of Eratosthenes

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly. I made this super simple, trying to learn a little bit about ...
9
votes
3answers
3k views

Sieve of Eratosthenes in Java

Here you can find my implementation of sieve of Eratosthenes in Java. ...
5
votes
2answers
811 views

Submitting a Java program which implements the Sieve of Eratosthenes

I would like some feedback on a Java program which implements the Sieve of Eratosthenes to find prime numbers. Some of the 'features' I've included in the program include: It uses a ...
5
votes
3answers
730 views

Psycho and ordinary numbers

The problem statement can be found here. In short, here's what the problem is about: You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number ...
7
votes
1answer
466 views

Prime Numbers Store

Let's say we need to create a store for selling prime numbers. Users enter the store and ask to buy a number. If the number asked is a prime number, 1.1. then it's either available for sale 1.2. ...
14
votes
4answers
9k views

Sieve of Eratosthenes in C++

I'm looking for some feedback on my implementation of the algorithm. How can I improve it? I ran into problems when calculating the larger prime numbers > 46349 due to integer overflow, but fixed that ...
3
votes
1answer
427 views

Initialize a Sieve of Eratosthenes in Scala

I am learning Scala while solving some exercises and I am currently solving an exercise where I need to initialize a Sieve of Eratosthenes. I am using the following code: ...
8
votes
4answers
4k views

Sieve of Eratosthenes in C# with LINQ

Can someone look over this Sieve of Eratosthenes implementation? It seems almost too easy. Rather than maintaining a seperate bit[] to track prime/not prime, I'm ...
5
votes
1answer
2k views

Sieve of Eratosthenes - Standard and Optimized implementation

I am a Java developer who is taking Python for the first time. I'm sure this is not at all elegant since I am thinking more in C syntax. ...
11
votes
3answers
1k views

Parallel sieve of Eratosthenes, version 2

This question is a revision of Parallel sieve of Eratosthenes. The goal is to implement a sieve of Eratosthenes with parallel strikes out from the boolean array. I tried to fix the data races and all ...
40
votes
5answers
6k views

Parallel sieve of Eratosthenes

For the first time, I tried to use threads by myself in order to implement a parallel sieve of Eratosthenes. The trick is that each time a prime is found, a thread is spawned to eliminate all the ...

1 2 3
4