How to resolve the algorithm Sieve of Eratosthenes step by step in the V (Vlang) programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sieve of Eratosthenes step by step in the V (Vlang) programming language
Table of Contents
Problem Statement
The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.
Implement the Sieve of Eratosthenes algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes. If there's an easy way to add such a wheel based optimization, implement it as an alternative version.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sieve of Eratosthenes step by step in the V (Vlang) programming language
Source code in the v programming language
fn main() {
limit := 201 // means sieve numbers < 201
// sieve
mut c := []bool{len: limit} // c for composite. false means prime candidate
c[1] = true // 1 not considered prime
mut p := 2
for {
// first allowed optimization: outer loop only goes to sqrt(limit)
p2 := p * p
if p2 >= limit {
break
}
// second allowed optimization: inner loop starts at sqr(p)
for i := p2; i < limit; i += p {
c[i] = true // it's a composite
}
// scan to get next prime for outer loop
for {
p++
if !c[p] {
break
}
}
}
// sieve complete. now print a representation.
for n in 1..limit {
if c[n] {
print(" .")
} else {
print("${n:3}")
}
if n%20 == 0 {
println("")
}
}
}
You may also check:How to resolve the algorithm Fusc sequence step by step in the D programming language
You may also check:How to resolve the algorithm Knuth shuffle step by step in the Joy programming language
You may also check:How to resolve the algorithm Loops/Infinite step by step in the GML programming language
You may also check:How to resolve the algorithm Flatten a list step by step in the Perl programming language
You may also check:How to resolve the algorithm Loops/Do-while step by step in the SAS programming language