How to resolve the algorithm Sieve of Eratosthenes step by step in the FreeBASIC programming language

Published on 12 May 2024 09:40 PM
#Freebasic

How to resolve the algorithm Sieve of Eratosthenes step by step in the FreeBASIC 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 FreeBASIC programming language

Source code in the freebasic programming language

' FB 1.05.0

Sub sieve(n As Integer)
  If n < 2 Then Return
  Dim a(2 To n) As Integer
  For i As Integer = 2 To n : a(i) = i : Next
  Dim As Integer p = 2, q
  ' mark non-prime numbers by setting the corresponding array element to 0
  Do
    For j As Integer = p * p To n Step p
      a(j) = 0
    Next j
    ' look for next non-zero element in array after 'p'
    q = 0
    For j As Integer = p + 1 To Sqr(n)
      If a(j) <> 0 Then
        q = j
        Exit For
      End If
    Next j    
    If q = 0 Then Exit Do
    p = q
  Loop

  ' print the non-zero numbers remaining i.e. the primes
  For i As Integer = 2 To n
    If a(i) <> 0 Then
      Print Using "####"; a(i);      
    End If
  Next
  Print
End Sub

Print "The primes up to 1000 are :"
Print
sieve(1000)
Print
Print "Press any key to quit"
Sleep

You may also check:How to resolve the algorithm UPC step by step in the D programming language
You may also check:How to resolve the algorithm Horizontal sundial calculations step by step in the Delphi programming language
You may also check:How to resolve the algorithm Statistics/Normal distribution step by step in the Ruby programming language
You may also check:How to resolve the algorithm Collections step by step in the Oz programming language
You may also check:How to resolve the algorithm Elliptic Curve Digital Signature Algorithm step by step in the Java programming language