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 seconds. ``` $ ./a.out | head -1000000 | tail -1 15485863 $ ``` Just looking for general code review comments here. At least two parts of `sieverator` smell really bad to me, but I'm not sure of the proper way to fix them while still preserving the general "STLishness" of this code. For example, I really want to keep using the ranged for-loop in `main`. ``` #include #include #include #include #include #include template class iotarator { Int value = 0; Int step = 1; public: explicit iotarator() = default; explicit iotarator(Int v) : value(v) {} explicit iotarator(Int v, Int s) : value(v), step(s) {} Int operator*() const { return value; } iotarator& operator++() { value += step; return *this; } iotarator operator++(int) { auto ret = *this; ++*this; return ret; } bool operator==(const iotarator& rhs) const { return value == rhs.value && step == rhs.step; } bool operator!=(const iotarator& rhs) const { return !(*this == rhs); } }; template class sieverator { struct erased_iterator { virtual Int dereference() = 0; virtual void increment() = 0; }; template class derived_iterator : public erased_iterator { It it; public: derived_iterator(It it) : it(std::move(it)) {} Int dereference() override { return *it; } void increment() override { ++it; } }; Int m_current; std::unique_ptr m_ptr; explicit sieverator() {} // used by .end() public: template explicit sieverator(It it) : m_current(*it), m_ptr(std::make_unique>(std::move(it))) {} sieverator begin() { return std::move(*this); } sieverator end() const { return sieverator{}; } bool operator==(const sieverator&) const { return false; } bool op

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 `Sieve` which has two member functions: ``` unsigned Sieve::expand(unsigned upperlimit); ``` This expands the existing sieve up to the passed upper limit and attempts to minimize rework. That is, if the current sieve has an upper limit of 10 and the expansion request is 15, the code only processes the difference, i.e. the half open range (10, 15]. If the new requested limit is smaller, the code simply returns without doing anything. The other significant function is: ``` bool isPrime(unsigned n) const; ``` As one would expect, if `n` is not greater than the current upper limit, the returned `bool` is `true` if `n` is prime. If `n` is greater than the current limit, this function throws a `std::range_error`. The intent is that one could either catch an error or, better, always call `expand` before `isPrime`. The reason for not combining those within the class code is that I wanted to create a complete but minimal interface. The test code is simply a reinterpretation of the original code's interface. Specifically, it expects one integer to be the number of test cases, `T`, and then for each test case, a lower and upper integer (`m`, and `n`). For each test case, the code prints a list of prime numbers in the range [m, n] separated by spaces. The test code assumes correct input and does not, for example, check to assure that m < n. primes.cpp ``` #include #include #include #include #include class Sieve { public: Sieve(); unsigned expand(unsigned upperlimit); bool isPrime(unsigned n) const; private: unsigned limit; std::vector composite; }; Sieve::Sieve() : limit{0}, composite{} {} bool Sieve::isPrime(unsigned n) const { if (n > limit) throw std::range_error("n must be less than limit"); return n==2 || (n%

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 time limit? number-theory Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers! Input The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space. Output For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line. Example Input: 2 1 10 3 5 Output: 2 3 5 7 3 5 Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed) Time limit: 6s Source limit: 50000B Memory limit: 1536MB ``` #include #include #include int main() { int T; uint64_t m, n; std::scanf("%d", &T); while (T--) { std::scanf("%llu %llu", &m, &n); std::vector flags(n+1); std::fill(flags.begin(),flags.end(),true); if (m == 1) { m++; } double halfMax = ceil(sqrt(n)); for (uint64_t i = 2; i <= halfMax; ++i) { if (flags[i]) { for (uint64_t j = i * 2; j <= n; j += i) { flags[j] = false; } } } for (uint64_t k = m ; k <= n; ++k) { if (flags[k]) { printf("%lld", k); printf(" "); } } printf("\n"); } } ```

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 particular, is my code in the correct Rust style? I am aware of some changes to make the algorithm faster, but I would prefer feedback on the style of Rust code instead. ``` use std::env; use std::fs::File; use std::io::{Write, BufWriter}; fn prime_sieve(n: usize, ofile: &String) -> u32 { let f = File::create(ofile).expect("Unable to create file"); let mut f = BufWriter::new(f); let mut prime_mask: Vec = vec![true;n]; prime_mask[0] = false; prime_mask[1] = false; let mut p = 2; // First prime number let mut count = 0; // Total number of primes found let mut i; // Main sieve loop while p = env::args().collect(); let n: usize = args[1] .trim() .parse() .expect("Wanted a number"); let ofile = &args[2]; let np = prime_sieve(n,ofile); println!("Found {} primes less than {}. Wrote to {}", np, n, &args[2]); } ```

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 use `std::vector` on purpose because I didn't really know how to use pointers. I want to know if I am using the pointers correctly and if my coding style is good. ``` #include /* NULL */ #include /* malloc, free */ #include /* strcmp */ #include /* std::istringstream */ #include /* std::cout, std::cerr, std::endl */ /** * Returns the primes from 1 to as a std::size_t* that ends with a 0. * NULL if is negative or malloc or realloc returned NULL. */ std::size_t* prime_sieve(std::size_t limit) { if (limit > limit)) { std::cerr > limit)) { std::cerr << "Invalid integer given" << std::endl; return 1; } } if (limit < 0) { std::cerr << "Invalid integer given" << std::endl; return 1; } std::size_t* primes = prime_sieve(limit); if (primes == NULL) { // malloc or realloc returned NULL. std::cerr << "Ran out of memory" << std::endl; return 1; } std::size_t i = 0; if (std::size_t prime = primes[i++]) { // The first one has no space preceding it std::cout << prime; while (prime = primes[i++]) { std::cout << ' ' << prime; } } std::cout << std::endl; free(primes); return 0; } ``` And these results: ``` ~/primes$ ./primes.out 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ``` This is not meant to be extremely efficient, but here are the timings (taken from the `real` value from `time`): ``` 10: 0.012s (avg. of 200) 100: 0.012s (avg. of 200) 1000 (1K): 0.013s (avg. of 200) 10000: 0.013s (avg. of 200) 100000: 0.017s (avg. of 200) 1000000 (1M): 0.062s (avg. of 200) 10000000: 0.542s (avg. of 100) 100000000:

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 version runs much much quicker for n larger than 100,000. At n = 100,000 the Scala version runs in around a minute where as the Node.js one runs in milliseconds. As far as I know the Scala version is implemented correctly as it finds the first few primes correctly. The big disparity in time leads me to believe it's an algorithmic issue and the two pieces of code likely have different time complexities, but looking at the two pieces of code I don't see any stark differences other than iterating the list a couple extra times in the scala version (with the zipIndex and mapping). Any help would be appreciated. This is my Scala method `// Sieve of Eratosthenes // pseudo code from https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve (n: Integer) = { // Let A be an array of Boolean values, indexed by integers 2 to n, // initially all set to true. var A = new ListBuffer[Boolean]() var i = 2 for (i b }.map{ case (b, i) => i + 2 }; } ` This is my Node.js code: `let _ = require('lodash'); // Sieve of Eratosthenes // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes function int (str, base=10) { return parseInt(str, base); } // Input: an integer n > 1. let n = int(process.argv[2]); // Let A be an array of Boolean values, indexed by integers 2 to n, // initially all set to true. let A = _.range(n+1) A[0] = false A[1] = false // for i = 2, 3, 4, ..., not exceeding √n: // if A[i] is true: // for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n: // A[j] := false. for(let i = 2; i el); `

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 size to sieve values, I keep an ordered set of upcoming composite values which are updated as they are reached. ``` #include unsigned long find_nth_prime(unsigned long n) { if (!n) return 1; // "0th prime" if (!--n) return 2; // first prime // The map m contains one entry for each prime. The key is the // next time to update it, and the value is the amount to increment // by each time it is reached. auto m = std::map(); // The overflow tests below are valid only for unsigned types. for (auto i = 3ul; true; i += 2) { if (i first != i) { // it's a prime if (!--n) return i; if (i*i > i) // overflow test m.insert({i*i, 2*i}); } else { // it's composite - advance the factor auto next = it->first; do { next += it->second; } while (next > i && !m.emplace(next, it->second).second); m.erase(it); } } } ``` And the test program (not really part of the review): ``` #include #include int main(int, char **argv) { std::cout.imbue(std::locale("")); while (*++argv) { try { std::cout << find_nth_prime(std::stoul(*argv)) << std::endl; } catch (std::exception&) { std::cerr << "Invalid argument: " << *argv << std::endl; } } } ``` Compiled with GCC: `g++ -std=c++17 -O3 -Wall -Wextra -Wpedantic ` Whilst the performance is acceptable (about 1.6 seconds on my hardware to find the one-millionth prime - 15,485,863), I'm unsure whether a `std::map` is really the best structure for keeping track. As usual, any other critique of the code is welcome.

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 some suggestions for optimizations that I can do to improve the efficiency of this algorithm? Input: The input begins with the number `t` of test cases in a single line (`t<=10`). In each of the next `t` lines there are two numbers `m` and `n` (`1 <= m <= n <= 1000000000`, `n-m<=100000`) separated by a space. Output: For every test case print all prime numbers `p` such that `m <= p <= n`, one number per line, test cases separated by an empty line. ``` #include #include #include using namespace std; typedef vector VB; typedef vector VI; VI sieve(int n) { VB is_prime(n, true); int sqrtn = sqrt(n); for (int i = 2; i = m && i != prime) { is_prime[i - m] = false; } } } for (int k = 0; k <= range; ++k) { if (is_prime[k]) { printf("%d\n", m + k); } } } int main() { int t; scanf("%d", &t); while (t--) { int m, n; scanf("%d%d", &m, &n); if (m == 1) m++; segmented_sieve(m, n); } return 0; } ```

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. However, when asking for the 1000th prime number I already notice a significant lag on my box. This code needs to be able to quickly return the \$n\$th prime where \$n\$ is a massive number. For the challenge I only need to get up to 200,000. However, being able to finalize this for efficient use for up to a million would be pretty awesome, I think. This is what I have working so far: ``` def nthPrime(ind): #gets nth prime number. IE: 5th prime == 11. works based off very in-efficient version of Sieve of Eratosthenes. but in increments of 200 p={} T = 2 incST = 2 incEND = incST + 200 lenfinal = 1 while lenfinal = incST: p[T**2 + (T*l)] = False l+=1 if T**2+(T*l) > incEND: break for k,v in sorted(p.items()): if v and k > T: T = int(k) break incST = incEND + 1 incEND = incST + 200 lenfinal = sum(1 for k,v in p.items() if v) final = [k for k,v in sorted(p.items()) if v] return final[ind-1] ```

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 extremely useful in writing my programs. I have now expanded on this program to look at the difference in the amount of primes up to a certain point according to a lower bound, and the amount of "straight inhibitors" up to a certain point. A straight inhibitor is a figment of my imagination that I have used in my math and is extremely important for it. ``` import math grandtotal = 1000 def prime_sieve(limit): a = [True] * limit a[0] = a[1] = False for i, isprime in enumerate(a): if isprime: yield i for n in xrange(i * i, limit, i): a[n] = False def getDotArrayLog(): e=55 data = [] while e<grandtotal: e+=1 data.append((2 * e / (math.log(2.0 * e, 10) + 2)) - e / (math.log(e, 10) - 4)) return data def getDotArrayProduct(): e=55 data = [] product = 1.0 while True: if e==grandtotal: break e+=1 for p in prime_sieve(e): product *= (1.0 - 1.0 / p) data.append(product) product = 1.0 return data if __name__ == "__main__": logs = getDotArrayLog() producta = getDotArrayProduct() print "Tested all the way up to", grandtotal counter = 0 for e in logs: a = (1-producta[counter])*(counter+55) print "Amount of primes:", e print "Amount of inhibitors:", a print e-a counter+=1 ``` I'm looking for some optimizations, condensations, and probably a great lecture on proper conventions.