PrimePrinter

In questo esempio vedremo l'applicazione del principio SRP (Single Responsibility Principle) per la creazione di un sistema che si occupa di generare e stampare, sotto forma di righe-colonne, i primi 1000 numeri primi.

PrimeGenerator

<?php

/**
 * Questa classe genera dei numeri primi fino a un massimo specificato dall'utente.
 * L'algoritmo usato è il Setaccio di Eratostene.
 * Dato un array di interi a partire da 2:
 * - trova il primo intero non eliminato ed elimina tutti i suoi multipli
 * - ripeti finché non vi sono più multipli nell'array
 */
class PrimeGenerator
{
    private static $crossedOut = [];
    private static $result = [];

    public static function generate(int $maxValue): array
    {
        if ($maxValue < 2) {
            return [];
        }

        self::uncrossIntegersUpTo($maxValue);
        self::crossOutMultiples();
        self::putUncrossedIntegersIntoResult();

        return self::$result;
    }

    private static function uncrossIntegersUpTo(int $maxValue): void
    {
        for ($i = 0; $i < $maxValue + 1; $i++) {
            self::$crossedOut[$i] = false;
        }
    }

    private static function crossOutMultiples(): void
    {
        $limit = self::determineIterationLimit();
        for ($i = 2; $i <= $limit; $i++) {
            if (self::notCrossed($i)) {
                self::crossOutMultiplesOf($i);
            }
        }
    }

    /**
     * Ogni multiplo nell'array ha un fattore primo che è minore o uguale alla radice
     * delle dimensioni dell'array, così che possiamo evitare di eliminare i multipli
     * dei numeri maggiori di tale radice
     * @return int
     */
    private static function determineIterationLimit(): int
    {
        return (int)sqrt(count(self::$crossedOut));
    }

    private static function notCrossed(int $i): bool
    {
        return self::$crossedOut[$i] === false;
    }

    private static function crossOutMultiplesOf(int $i): void
    {
        for ($multiple = 2 * $i; $multiple < count(self::$crossedOut); $multiple += $i) {
            self::$crossedOut[$multiple] = true;
        }
    }

    private static function putUncrossedIntegersIntoResult()
    {
        for ($j = 0, $i = 2; $i < count(self::$crossedOut); $i++) {
            if (self::notCrossed($i)) {
                self::$result[$j++] = $i;
            }
        }
    }
}

RowColumnPagePrinter

PrimePrinter

Index

Last updated

Was this helpful?