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

Published on 12 May 2024 09:40 PM
#Processing

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

Source code in the processing programming language

int i=2;
int maxx;
int maxy;
int max;
boolean[] sieve;

void setup() {
  size(1000, 1000);
  // frameRate(2);
  maxx=width;
  maxy=height;
  max=width*height;
  sieve=new boolean[max+1];

  sieve[1]=false;
  plot(0, false);
  plot(1, false);
  for (int i=2; i<=max; i++) {
    sieve[i]=true;
    plot(i, true);
  }
}

void draw() {
  if (!sieve[i]) {
    while (i*i<max && !sieve[i]) {
      i++;
    }
  }
  if (sieve[i]) {
    print(i+" ");
    for (int j=i*i; j<=max; j+=i) {
      if (sieve[j]) {
        sieve[j]=false;
        plot(j, false);
      }
    }
  }
  if (i*i<max) {
    i++;
  } else {
    noLoop();
    println("finished");
  }
}

void plot(int pos, boolean active) {
  set(pos%maxx, pos/maxx, active?#000000:#ffffff);
}

from __future__ import print_function

i = 2

def setup():
    size(1000, 1000)
    # frameRate(2)
    global maxx, maxy, max_num, sieve
    maxx = width
    maxy = height
    max_num = width * height
    sieve = [False] * (max_num + 1)

    sieve[1] = False
    plot(0, False)
    plot(1, False)
    for i in range(2, max_num + 1):
        sieve[i] = True
        plot(i, True)


def draw():
    global i
    if not sieve[i]:
        while (i * i < max_num and not sieve[i]):
            i += 1

    if sieve[i]:
        print("{} ".format(i), end = '')
        for j in range(i * i, max_num + 1, i):
            if sieve[j]:
                sieve[j] = False
                plot(j, False)

    if i * i < max_num:
        i += 1
    else:
        noLoop()
        println("finished")


def plot(pos, active):
    set(pos % maxx, pos / maxx, color(0) if active else color(255))

You may also check:How to resolve the algorithm Factors of an integer step by step in the Gosu programming language
You may also check:How to resolve the algorithm Calendar step by step in the Phixmonti programming language
You may also check:How to resolve the algorithm Minimum multiple of m where digital sum equals m step by step in the C++ programming language
You may also check:How to resolve the algorithm Set of real numbers step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Date format step by step in the Maple programming language