We’re rewarding the question askers & reputations are being recalculated! Read more.

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
56 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 ...
1
vote
1answer
388 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
0answers
55 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 ...
1
vote
0answers
103 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
3answers
93 views

Short Eratosthenes Sieve

I've written a short implementation of the Eratosthenes' sieve. ...
0
votes
1answer
186 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
121 views

A non-static Sieve of Eratosthenes class, version 1

Over the years I’ve seen many C# sieves and despite their varying internals all that I have seen invariably are a static method that returns a List<int>, ...
0
votes
2answers
93 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? ...
0
votes
1answer
53 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: ...
-1
votes
1answer
745 views

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

How can I optimize this? ...