Prime number decomposition

README.md

Prime number decomposition

Installation

Download composer.phar from https://getcomposer.org/

curl -sS https://getcomposer.org/installer | php

Install dependencies

php composer.phar install

Usage

Run unit tests

vendor/bin/phpunit PrimeNumberDecompositionTest.php

composer.json

{
    "require-dev": {
        "phpunit/phpunit": "4.*"
    },
    "autoload": {
        "files": ["PrimeNumberDecomposition.php"]
    }
}

PrimeNumberDecomposition.php

<?php

class PrimeNumberDecomposition
{
    public static function Generate($number)
    {
        if (self::isPrime($number)) {
            return [$number];
        }

        for ($n = 2; $n < $number; $n++) {
            if (self::isPrime($n) && $number % $n == 0) {
                $left = $number / $n;
                if (self::isPrime($left)) {
                    return [$n, $left];
                } else {
                    return array_merge([$n], self::Generate($left));
                }
            }
        }

        return [];
    }

    public static function isPrime($number)
    {

        for ($n = 2; $n < $number; $n++) {
            if ($number % $n === 0) {
                return false;
            }
        }

        return true;
    }
}

PrimeNumberDecompositionTest.php

<?php

// Composer genereated autoloader
require __DIR__ . '/vendor/autoload.php';

class PrimeNumberDecompositionTest extends PHPUnit_Framework_TestCase
{
    public function myTestProvider()
    {
        return array(
            array(2, [2]),
            array(3, [3]),
            array(4, [2, 2]),
            array(6, [2, 3]),
            array(8, [2, 2, 2]),
            array(9, [3, 3]),
            array(32, [2, 2, 2, 2, 2]),
            array(43890, [2, 3, 5, 7, 11, 19]),
            array(988027, [991, 997]),
            array(13082761331670030, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]),
        );
    }


    /**
     * @dataProvider myTestProvider
     */
    public function testPrimeDecomposition($number, $result)
    {
        $this->assertEquals($result, PrimeNumberDecomposition::Generate($number));
    }

    public function myPrimeDataProvider()
    {
        return array(
            array(1, true),
            array(2, true),
            array(3, true),
            array(4, false),
            array(5, true),
            array(6, false),
            array(11, true),
            array(331, true),
        );
    }

    /**
     * @dataProvider myPrimeDataProvider
     */
    public function testIsPrime($number, $result)
    {
        $this->assertEquals($result, PrimeNumberDecomposition::isPrime($number));
    }
}